Marked Runs in a Chain

Medium

You get a singly linked list head whose values are all distinct, and an array marked holding some of those values (also distinct, in any order). Mark the nodes whose values appear in marked. Walking the list from start to end, count how many unbroken runs the marked nodes form. Two marked nodes belong to the same run when there is no unmarked node between them.

Example 1

head=list_node([3, 0, 4, 1, 2]), marked=[0, 4, 2] → 2

The marked values 0 and 4 sit next to each other and form one run; 1 is not marked, and 2 forms a second run.

Example 2

head=list_node([5, 2, 7]), marked=[7, 5, 2] → 1

Every node is marked, so the whole list is one run. The order inside marked does not matter.

Constraints

1 ≤ number of nodes ≤ 10⁵
0 ≤ Node.val ≤ 10⁵, all values distinct
1 ≤ len(marked) ≤ number of nodes
The values in marked are distinct and all occur in the list

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Linked List

Similar problems

Purge Banned Values Medium Sudoku Board Without Clashes Medium Anagram Buckets Medium Zero Out the Crosses Medium Tree From Pre-Order and In-Order Walks Medium

Input

head=list_node([3, 0, 4, 1, 2]), marked=[0, 4, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.