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^51 <= nums[i] <= 10^81 <= value <= 10^850000 calls will be made to showFirstUnique and add.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Map + Linear Scan | O(n) per showFirstUnique | O(n) | Simple baseline solution when performance is not critical |
| Queue + Hash Map (Lazy Removal) | O(1) amortized | O(n) | Best for real-time data streams where you must track the first unique element efficiently |
| Ordered Set + Hash Map | O(1) average | O(n) | Alternative design using ordered sets (e.g., LinkedHashSet) to directly track unique elements |
First Unique Number (LeetCode Day 28) • Errichto Algorithms • 21,948 views views
Watch 9 more video solutions →Practice First Unique Number with our built-in code editor and test cases.
Practice on FleetCode