First Unique Number
Problem
Design a data structure over a stream of integers that supports two operations. add(value) appends a number to the stream, and showFirstUnique() returns the first number that has appeared exactly once so far, in the order it arrived. If every number seen so far is a duplicate (or the stream is empty), return -1.
initial = [2, 3, 5], then add(5), add(2), add(3)2, 2, 3, -1class FirstUnique:
def __init__(self, nums):
self.count = {}
self.queue = deque()
for x in nums:
self.add(x)
def add(self, value):
self.count[value] = self.count.get(value, 0) + 1
if self.count[value] == 1:
self.queue.append(value)
def show_first_unique(self):
while self.queue and self.count[self.queue[0]] > 1:
self.queue.popleft()
return self.queue[0] if self.queue else -1class FirstUnique {
constructor(nums) {
this.count = new Map();
this.queue = [];
for (const x of nums) this.add(x);
}
add(value) {
this.count.set(value, (this.count.get(value) || 0) + 1);
if (this.count.get(value) === 1) this.queue.push(value);
}
showFirstUnique() {
while (this.queue.length && this.count.get(this.queue[0]) > 1)
this.queue.shift();
return this.queue.length ? this.queue[0] : -1;
}
}class FirstUnique {
Map<Integer, Integer> count = new HashMap<>();
Deque<Integer> queue = new ArrayDeque<>();
public FirstUnique(int[] nums) {
for (int x : nums) add(x);
}
public void add(int value) {
count.put(value, count.getOrDefault(value, 0) + 1);
if (count.get(value) == 1) queue.addLast(value);
}
public int showFirstUnique() {
while (!queue.isEmpty() && count.get(queue.peekFirst()) > 1)
queue.pollFirst();
return queue.isEmpty() ? -1 : queue.peekFirst();
}
}class FirstUnique {
unordered_map<int, int> count;
deque<int> queue;
public:
FirstUnique(vector<int>& nums) {
for (int x : nums) add(x);
}
void add(int value) {
count[value]++;
if (count[value] == 1) queue.push_back(value);
}
int showFirstUnique() {
while (!queue.empty() && count[queue.front()] > 1)
queue.pop_front();
return queue.empty() ? -1 : queue.front();
}
};Explanation
The naive way to answer showFirstUnique() would be to scan the whole stream every time, counting how often each number appears and returning the first one with a count of one. That re-scans everything on every query, which is slow when there are many calls.
The smarter idea pairs a queue with a frequency map. The map (value → how many times we have seen it) is the source of truth for whether a number is currently unique. The queue holds candidate uniques in arrival order, so the front of the queue is always the earliest number that might still be unique.
On add(value) we bump its count. If this is the first time we have seen it (count became 1), we push it to the back of the queue. We never need to remove it on a later duplicate add — the map already knows it is no longer unique, and we will clean it out lazily.
On showFirstUnique() we peek the front of the queue. If the front's count is greater than 1 it is stale (it became a duplicate after being enqueued), so we pop it and keep going. The moment the front has count exactly 1, that is our answer. If the queue empties, every number is a duplicate, so we return -1.
Trace the example: after [2, 3, 5] the queue is [2, 3, 5] and counts are all 1, so the front 2 is unique → 2. add(5) raises 5's count to 2 but the front is still 2 → 2. add(2) raises 2's count to 2; now the front 2 is stale, we pop it, and 3 (count 1) surfaces → 3. add(3) raises 3's count to 2; popping 2, 3, and the duplicate 5 empties the queue → -1.
Each value is enqueued once and dequeued at most once, so all the lazy popping across the whole run adds up to linear work overall — every query is effectively constant time amortized.