AlgoMaster Logo

First Unique Number

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We're designing a data structure that maintains a queue of integers and supports two operations: adding a new integer and querying the first unique integer (an integer that appears exactly once across all values ever added).

The challenge is the interaction between these two requirements. When we add a new number, it might turn a previously unique number into a duplicate. And when we query, we need to quickly find the first number (in insertion order) that still has a count of exactly one. A naive approach that rescans everything on each query will be too slow when there are tens of thousands of operations.

"First unique" means we care about insertion order among the elements that still appear exactly once. We need a data structure that maintains that order and also allows efficient removal when an element stops being unique.

Key Constraints:

  • 1 <= nums.length <= 10^5 → The initial queue can be large, so initialization should be at most O(n).
  • At most 5 * 10^4 calls to showFirstUnique and add → Both operations need to be efficient. If showFirstUnique is O(n) per call, the worst case is O(n q) which could be 5 10^9. We should aim for O(1) amortized for showFirstUnique.
  • 1 <= nums[i] <= 10^8 → Values can be large, so a fixed-size array won't work. We need a hash map.

Approach 1: Brute Force (Queue + Hash Map Scan)

Intuition

Use a list to store all added numbers in order, and a hash map to track the count of each number. When showFirstUnique is called, iterate through the list from the beginning and return the first number whose count is exactly 1.

The cost lives in the query. Each showFirstUnique call may scan through many duplicate entries before finding a unique one, or reach the end without finding any.

Algorithm

  1. Maintain a list queue that stores all numbers in insertion order.
  2. Maintain a hash map count that stores the frequency of each number.
  3. For add(value): append value to the list and increment its count in the map.
  4. For showFirstUnique(): iterate through the list from the start. Return the first element whose count is exactly 1. If none exists, return -1.

Visualization and Code

Loading animation...

Every call to showFirstUnique rescans from the beginning, skipping over duplicates. Once a number becomes a duplicate, it never becomes unique again, yet we keep scanning past it. The next approach removes a number from the ordered structure the moment it stops being unique, so the first element is always the answer.

Approach 2: LinkedHashSet (Ordered Set + Hash Map)

Intuition

If we remove elements from the ordered collection the moment they become duplicates, the first element is always the first unique number, and showFirstUnique never has to scan.

A regular queue does not support efficient removal from the middle. A LinkedHashSet (in Java) or OrderedDict (in Python) gives us both insertion-order iteration and O(1) removal. We maintain this set alongside a hash map of counts. When a number's count goes above 1, we remove it from the set. The first element of the set is the answer.

For languages without a built-in ordered set, we build one from a doubly linked list plus a hash map from values to nodes. The hash map locates a node in O(1); the doubly linked list lets us unlink it in O(1) and still iterate in insertion order.

Algorithm

  1. Maintain an ordered set uniqueSet that only contains numbers with count exactly 1, in insertion order.
  2. Maintain a hash map count that tracks the frequency of every number.
  3. For add(value): increment the count. If count becomes 1, add to the ordered set. If count becomes 2, remove from the ordered set.
  4. For showFirstUnique(): return the first element of the ordered set. If the set is empty, return -1.

Visualization and Code

Loading animation...

Approach 2 gives O(1) worst case for both operations, at the cost of either a language-specific ordered set or a custom doubly linked list. The next approach reaches the same amortized performance with a plain queue and no node bookkeeping.

Approach 3: Queue with Lazy Deletion

Intuition

Instead of removing duplicates from the queue the moment they appear, we use a regular queue and skip over stale entries during the query.

Maintain a queue of values in insertion order, plus a hash map of counts. When showFirstUnique is called, peek at the front of the queue. If that value has count > 1, it is a duplicate, so pop it and check the next one. Keep popping until the front has count == 1, or the queue is empty.

This is lazy deletion. We leave stale elements in the queue and discard them only when they reach the front during a query. Each element is popped at most once, so across all showFirstUnique calls the total popping work is O(n), which makes each query O(1) amortized.

Algorithm

  1. Maintain a queue q that stores values in insertion order.
  2. Maintain a hash map count that tracks the frequency of each value.
  3. For add(value): increment count. If this is the first time seeing the value (count becomes 1), enqueue it.
  4. For showFirstUnique(): while the queue is not empty and the front element has count > 1, dequeue it (lazy deletion). If the queue is not empty, return the front. Otherwise return -1.

Visualization and Code

Loading animation...