DSA problem

First Unique Number

MediumQueuesPattern: Queuestop600AmazonMicrosoftGoogleBloombergMeta

You have a queue of integers, and you need to design a data structure that supports two operations: add(value) appends a new integer to the back of the queue, and showFirstUnique() returns the value of the first integer in the queue that has appeared exactly once so far. If no unique integer exists, return -1.

The straightforward approach is to scan the entire queue on each showFirstUnique call, looking for an element whose count is 1. That solution is O(n) per query and can degrade to O(n^2) across n queries on a long queue.

The optimal design separates concerns by maintaining two structures in parallel: a queue of candidate values that may still be the answer, and a hash map from value to its current count in the entire stream. On add(value), increment the count; if the value's count just became 1 push it to the back of the candidate queue. On showFirstUnique, evict from the front of the candidate queue while the front's count is greater than 1 — those candidates are no longer unique and cannot be the answer. Then either return the new front value or return -1 if the candidate queue became empty.

Each value enters the candidate queue at most once and leaves at most once, so the amortized cost per operation is O(1). The total memory is O(n) where n is the total number of distinct integers added so far. This pattern of "queue of still-valid candidates + count map" generalizes to many streaming problems where the answer depends on the first item satisfying a property.

Examples

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^8
• 1 <= value <= 10^8
• At most 50000 calls will be made to showFirstUnique and add.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

queuedesignhash-tabledata-stream

Browse all DSA problems