MediumArrayHash TableDesignQueueUpdated Sep 2026

1429. First Unique Number

Asked at Uber

Difficulty

Medium

Time

O(1) for add, amortized O(1) for

Space

O(n)

Pattern

Array

Companies

1

Problem

Design a class FirstUnique that models a stream of integers. Numbers are added to the back of the stream over time, and at any moment you can ask for the first number in the stream that appears exactly once.

Implement three methods:

  • FirstUnique(int[] nums) — build the object with an initial stream of numbers.
  • showFirstUnique() — return the value of the earliest number whose total count in the stream is exactly 1. If every number appears at least twice, return -1.
  • add(int value) — append value to the end of the stream.

A number can become unique again only if it was never seen before. Once a value appears a second time, it is never unique again, no matter how many more times it is added.

The stream and its first unique value

stream235523012345After adding 5, 2 and 3, only 3 still appears exactlyonce, so the answer is 3.
The stream grows on the right; we always report the leftmost value whose total count is exactly 1.

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

Examples

Example 1
Input["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output[null,2,null,2,null,3,null,-1]
WhyStart with [2,3,5]: 2 is the first value seen only once. Adding 5 makes 5 a duplicate, but 2 is still unique, so the answer stays 2. Adding 2 also makes 2 a duplicate, so the earliest unique value is now 3. Adding 3 kills the last unique value, so the answer becomes -1.
Example 2
Input["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"] [[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output[null,-1,null,null,null,null,null,17]
WhyAll six starting values are 7, so nothing is unique and the first query returns -1. The adds keep repeating 7 and 3, which are already duplicates. Only 17 is new, so it is the single unique value at the end.
Example 3
Input["FirstUnique","showFirstUnique","add","showFirstUnique"] [[[809]],[],[809],[]]
Output[null,809,null,-1]
Why809 starts alone, so it is unique. After adding 809 again it appears twice and can never be unique again, so the second query returns -1.

Asked At

1 companies
CompanyDifficulty
UberMediumView all Uber questions →

How to Think About It

1

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.

2

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).

3

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.

4

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.

5

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):

  1. count[num] += 1
  2. If count[num] == 1, append num to queue.

firstUnique():

  1. While queue is not empty and count[queue[0]] > 1, pop from front.
  2. If queue is empty, return -1.
  3. 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).

Count map plus a lazy queue

queue23frontbackAfter add(2), add(3): both are unique, so both sit inthe queue in order.queue23frontbackadd(2) makes count[2] = 2, but 2 stays in the queue —we remove it lazily.queue3frontbackshowFirstUnique() pops 2 because its count is 2, thenreturns 3 whose count is 1.add: count[v] += 1; if count[v] == 1: push vquery: while front has count > 1: popanswer = front, or -1 if empty
The queue keeps candidates in arrival order; stale entries are thrown away only when we look at the front.
ComplexityTime O(1) for add, amortized O(1) forSpace O(n)Each distinct value enters the candidate queue at most once and leaves it at most once, so the total work across all queries is linear.

What Trips People Up in Real Interviews

1

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().

2

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.

3

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.

4

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).

5

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

O(1) for add, amortized O(1) for time
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)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(1) for add, amortized O(1) for time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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)`.