338. Connected Pieces
A necklace is stored as a chain of beads, each bead carrying a number, with the first bead at head. A jeweller has marked some numbers as precious and lists them in the array values; every number in this array appears only once. A bead is called precious when its number appears in values.
Cut the necklace into maximal pieces, where a piece is a group of precious beads that follow one another directly in the chain with no ordinary bead in between. Return how many such pieces the necklace contains. A chain with no precious beads has zero pieces, and two precious beads separated by even one ordinary bead belong to different pieces. The chain and the array can each hold 100,000 entries, so searching the array again for every bead is too slow.
Example 1
- Input:
- head = [4,9,9,2,7,4,4,1,9], values = [9,4,1]
- Output:
- 2
- Explanation:
The ordinary beads 2 and 7 split the precious ones into the pieces 4, 9, 9 and then 4, 4, 1 and finally the last 9, so the answer is 3.
Example 2
- Input:
- head = [30,31,32,33], values = [32,30]
- Output:
- 2
- Explanation:
30 is precious but 31 is not, so 30 is alone; 32 is next to the ordinary 31 and 33, so it is alone as well. Two pieces.
Constraints
0 ≤ chain length, values length ≤ 105
0 ≤ node value, values[i] ≤ 106
All numbers in values are distinct.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(V)