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.

Hint: An ID only stops being unique once

Counts tell you whether a candidate still qualifies. Each queued candidate can be discarded permanently when it reaches the head and is no longer unique.

Track the Earliest ID Posted Exactly Once

Approach

Count each ID up to two, since larger counts have identical permanent-disqualification behavior. Append an ID to a queue only on its first post. After every post, advance the head past candidates whose count is no longer one. The queue preserves first-post order, and all discarded candidates are permanently ineligible, so its first remaining element is exactly the earliest single visit. Getters only read this already-clean head and therefore take O(1) worst-case time. A post may trigger a long cleanup, but each distinct ID enters once and the head passes it once, giving expected amortized O(1) posting and O(n) total processing. Moving cleanup into getters would make getters only amortized constant, contrary to the stricter target. A doubly linked ordered set of currently unique IDs plus ID-to-node lookup can remove the repeated ID directly and expose the first unique node; it adds link management and still needs permanent repeated-ID state. The array queue retains old entries, using O(u) space for u distinct posted IDs.

• Time complexity: Expected O(n) total; O(1) getter, amortized O(1) post
• Space complexity: O(u) state for distinct IDs, plus output