Return the Earliest ID Seen Exactly Once

Maintain the earliest ID that has been posted exactly once so far. Support posting an ID and querying the current earliest single visit.

Implement earliest_single_visits(operations: int[][]) -> int[].

Constraints & Assumptions

• A row [0,id] represents post(id). A row [1] represents getEarliestSingleVisit().
• IDs are integers from 0 through 1000000; -1 is reserved for no qualifying ID.
• At most 300000 operations. Return one integer for each query, in query order; posting produces no output entry.
• “Earliest” means earliest first-post position among IDs whose total count is exactly one. Once an ID has been posted twice, it never qualifies again.
• All state fits in memory. Aim for O(1) query time and amortized O(1) posting time. Explain whether your chosen implementation instead shifts amortized cleanup work into queries.

Example

operations = [[0,1],[0,3],[1],[0,1],[0,5],[1]]
result = [1,3]

operations = [[1],[0,7],[0,7],[1],[0,7],[1]]
result = [-1,-1,-1]

The reported follow-up suggests pruning repeated IDs from a queue's head. Explain the invariant that makes its head the earliest remaining single ID and why total pruning work is amortized linear. If strict O(1) getters are required, decide when that pruning must occur. Compare with maintaining only unique IDs in an ordered linked structure.