First Unique Number
Asked at Uber
Problem
Design a data structure that accepts a stream of integers and returns the first unique number at any point. When add() is called, the number is appended to the stream. firstUnique() returns the first number that appears exactly once, or -1 if none exists.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | Medium | View all Uber questions → |
How to Think About It
Core data structures: a hash map counting occurrences, and a queue maintaining the order of unique candidates. The queue holds numbers that appeared exactly once, in the order they were added.
add(num): increment count in the hash map. If count becomes 1, enqueue it (it's a candidate). If count becomes 2, it's no longer unique, but DON'T remove it from the queue yet (lazy removal).
firstUnique(): pop from the front of the queue while the front element's count in the hash map is > 1 (it was made non-unique by a later add). Once you find a front with count == 1, return it. If queue empties, return -1.
Visual walkthrough:
add(1): count={1:1}, queue=[1]
add(2): count={1:1,2:1}, queue=[1,2]
add(1): count={1:2,2:1}, queue=[1,2] (1 stays, lazy removal)
firstUnique(): front=1, count=2 > 1, pop. front=2, count=1, return 2.
add(3): count={1:2,2:1,3:1}, queue=[2,3]
firstUnique(): front=2, count=1, return 2.
Why lazy removal works: you only remove from the front when querying. Each number is enqueued at most once and dequeued at most once. Total operations: O(n) for n add() and firstUnique() calls. No expensive queue scanning.
Time: add() is O(1), firstUnique() is amortized O(1) because each element is removed from the queue at most once. Space: O(n) for the hash map and queue.
Optimal Approach
Data structures: count (hash map, number -> frequency), queue (ordered unique candidates).
add(num):
count[num] += 1- If
count[num] == 1, append num to queue.
firstUnique():
- While queue is not empty and
count[queue[0]] > 1, pop from front. - If queue is empty, return -1.
- Return queue[0].
Walkthrough: add(2), add(3), add(2), firstUnique(), add(4), firstUnique().
- add(2): count={2:1}, queue=[2]
- add(3): count={2:1,3:1}, queue=[2,3]
- add(2): count={2:2,3:1}, queue=[2,3]
- firstUnique(): front=2, count=2, pop. front=3, count=1, return 3.
- add(4): count={2:2,3:1,4:1}, queue=[3,4]
- firstUnique(): front=3, count=1, return 3.
Time: add() O(1). firstUnique() amortized O(1). Space: O(n).
What Trips People Up in Real Interviews
Eagerly removing non-unique elements from the queue. Don't iterate and remove from the middle of a queue, it's O(n). Use lazy removal: only pop from the front during firstUnique().
Forgetting to handle the edge case where the stream is empty. firstUnique() should return -1 if no elements have been added. Initialize with an empty queue and empty map.
Treating the queue as storing only unique elements permanently. A number added when unique can become non-unique later. The queue doesn't track this; the hash map does. The queue just stores the order.
Not handling duplicate adds to the queue. When count becomes 1, enqueue. When it becomes 2 or more, do NOT enqueue again. Only enqueue on the first occurrence (count == 1 after increment).
Returning the first unique number by scanning the queue. You need the count hash map to check uniqueness. Scanning the queue and counting each time is O(n²) instead of amortized O(1).
Solution Code
from collections import deque, Counter
class FirstUnique:
def __init__(self, nums):
self.count = Counter(nums)
self.queue = deque()
for num in nums:
if self.count[num] == 1:
self.queue.append(num)
def showFirstUnique(self):
while self.queue and self.count[self.queue[0]] > 1:
self.queue.popleft()
return self.queue[0] if self.queue else -1
def add(self, num):
self.count[num] += 1
if self.count[num] == 1:
self.queue.append(num)Frequently Asked Questions
What is the First Unique Number problem?
Design a data structure that accepts a stream of integers and returns the first unique number at any point. When add() is called, the number is appended to the stream. firstUnique() returns the first number that appears exactly once, or -1 if none exists.
How do you solve First Unique Number?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask First Unique Number?
First Unique Number is asked at Uber. It is a medium difficulty problem.
What are common mistakes on First Unique Number?
- Eagerly removing non-unique elements from the queue. Don't iterate and remove from the middle of a queue, it's `O(n)`. Use lazy removal: only pop from the front during `firstUnique()`.
- Forgetting to handle the edge case where the stream is empty. `firstUnique()` should return -1 if no elements have been added. Initialize with an empty queue and empty map.
- Treating the queue as storing only unique elements permanently. A number added when unique can become non-unique later. The queue doesn't track this; the `hash map` does. The queue just stores the order.
- Not handling duplicate adds to the queue. When count becomes 1, enqueue. When it becomes 2 or more, do NOT enqueue again. Only enqueue on the first occurrence (count == 1 after increment).
- Returning the first unique number by scanning the queue. You need the count `hash map` to check uniqueness. Scanning the queue and counting each time is `O(n²)` instead of amortized `O(1)`.