Skip to main content
Talentd

First Unique Number - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableDesignQueue5 min readAsked at: Amazon, Microsoft, Uber +2
Practice this problem

Problem Statement

You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

  • FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
  • int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
  • void add(int value) insert value to the queue.

 

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]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -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]
Explanation: 
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // return -1
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3]
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7]
firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17]
firstUnique.showFirstUnique(); // return 17

Example 3:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
Output: 
[null,809,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // return 809
firstUnique.add(809);          // the queue is now [809,809]
firstUnique.showFirstUnique(); // return -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.

Approach Overview

Problem Overview: Design a data structure that processes a stream of integers and always returns the first number that appears exactly once. The class must support two operations: showFirstUnique() to get the current first unique value, and add(value) to insert a new number into the stream.

Approach 1: Frequency Map + Linear Scan (Brute Force) (Time: O(n) per query, Space: O(n))

Store all numbers in an array representing the stream and maintain a frequency count using a hash table. Each time showFirstUnique() is called, iterate through the array from the beginning and return the first value whose frequency is exactly one. The add(value) operation simply appends to the array and updates the frequency map. This approach is straightforward but inefficient because every query may scan the entire list, leading to O(n) time per lookup.

Approach 2: Queue + Hash Map (Optimal Data Stream Design) (Time: O(1) amortized, Space: O(n))

The optimal design uses a queue to maintain the order of candidates and a hash map to track frequencies. When a new value arrives through add(value), increment its count in the map and push it into the queue. When showFirstUnique() runs, repeatedly check the front of the queue. If its frequency is greater than one, remove it because it is no longer unique. The first element that still has frequency one becomes the answer.

This technique is often called lazy cleanup. Instead of removing duplicates immediately, you postpone removal until they appear at the front of the queue. Each element is inserted and removed at most once, which keeps operations amortized O(1). The design fits naturally with streaming problems and interview questions involving ordered uniqueness.

The solution combines ideas from hash tables for constant-time frequency lookup and a design-style data structure that preserves insertion order. Because the stream can grow indefinitely, avoiding repeated scans is critical for performance.

Recommended for interviews: Interviewers expect the queue + hash map approach. The brute force scan shows you understand the requirement, but it does not scale. The optimal design demonstrates knowledge of data stream processing and amortized analysis. Explaining why lazy removal keeps operations O(1) is usually the key insight they want to hear.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Map + Linear ScanO(n) per showFirstUniqueO(n)Simple baseline solution when performance is not critical
Queue + Hash Map (Lazy Removal)O(1) amortizedO(n)Best for real-time data streams where you must track the first unique element efficiently
Ordered Set + Hash MapO(1) averageO(n)Alternative design using ordered sets (e.g., LinkedHashSet) to directly track unique elements

Video Solution

First unique number | Leetcode • Techdose • 13,283 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is First Unique Number easy or hard?
First Unique Number is rated Medium difficulty. The challenge is designing a structure that maintains order while tracking duplicates efficiently. Once you combine a queue with a frequency hash map, the operations become straightforward and run in constant amortized time.
First Unique Number Python/Java solution
Implement a class that stores a queue and a hash map. The add(value) method increments the frequency and pushes the value into the queue. The showFirstUnique() method removes non-unique values from the queue front until a value with frequency 1 remains. The same logic works in Python, Java, C++, and Go.
How to solve First Unique Number in O(n)?
Process the stream using a hash map to store frequencies and a queue to keep insertion order. Every add(value) updates the frequency and pushes the value into the queue. When querying the first unique value, repeatedly remove the queue's front while its frequency is greater than one. Each element is processed at most twice, giving O(n) total work over n operations.
What is the best approach for First Unique Number?
The best approach uses a queue combined with a hash map. The hash map tracks the frequency of each number, while the queue preserves insertion order of candidates. During showFirstUnique(), remove elements from the front of the queue until the front has frequency 1. This results in O(1) amortized time for both add and query operations.
Is First Unique Number asked at Google/Amazon/Meta?
First Unique Number is a common design-style interview problem similar to questions asked at companies like Amazon, Google, and Meta. It tests understanding of hash maps, queues, and efficient data stream processing rather than complex algorithms.
What data structure is used in First Unique Number?
The typical solution uses a queue to maintain order and a hash map to store frequencies. Some implementations also use an ordered set such as LinkedHashSet to track unique elements directly. These structures allow constant-time updates and quick access to the first unique number.
What is the time complexity of First Unique Number?
Using the optimal queue and hash map design, both add() and showFirstUnique() run in O(1) amortized time. Each number is inserted into the queue once and removed at most once. The space complexity is O(n) to store the stream and frequency counts.

Ready to solve this problem?

Practice First Unique Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays