Setlist rank tracker: hints, no solution
Hard · Linked list
A radio station keeps its live setlist as a queue. It starts with m tracks, numbered 1 to m, with track 1 at the head. The desk then sends operations, each written as a pair [kind, x].
Kind 0 adds a brand new track immediately after track x in play order, and x = 0 means the new track goes to the very front. New tracks are numbered m + 1, m + 2 and so on, in the order they are added. Kind 1 removes track x for good. Kind 2 asks where track x stands right now, counting the head as position 1.
Return the answer to every kind 2 operation, in order. Track x is always in the queue when it is named, and a removed track never returns.
The queue can hold hundreds of thousands of tracks and thousands of questions arrive, so walking from the head for every question is too slow. Aim for about (m + q) log (m + q) time, where q is the number of operations.
Examples
- Input
- m = 3, ops = [[2, 3], [0, 1], [2, 3], [1, 2], [2, 3], [2, 4]]
- Output
- [3, 4, 3, 2]
- Note
- Track 4 joins right after 1, giving 1, 4, 2, 3. Removing 2 leaves 1, 4, 3, so track 3 moves from position 4 to 3 and track 4 sits at 2.
- Input
- m = 0, ops = [[0, 0], [0, 0], [0, 1], [2, 1], [2, 2]]
- Output
- [2, 1]
- Note
- Track 1 starts the queue, track 2 goes in front of it, and track 3 goes right after 1, so the order is 2, 1, 3.
- Input
- m = 5, ops = [[1, 5], [0, 4], [2, 6]]
- Output
- [5]
- Note
- Track 5 leaves, then the new track 6 goes right after 4, which is now the tail, so it stands at position 5.
Constraints
- 0 <= m <= 1000000
- 0 <= ops.length <= 60000; each op is [kind, x] with kind 0, 1 or 2
- x is 0 (kind 0 only) or a track that is in the queue at that moment
- Every answer is between 1 and m + ops.length
Hint 1: a nudge
Try one question by hand. What would you need to count to know how many tracks stand in front of a given track, and why is that count slow to get by walking from the head?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.