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.

Description Hints 3 Solution Video 12:48

1429. First Unique Number

Medium57.8% acceptance5 companiesPremium elsewhere, free here

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.

Asked at 5 companies

Uber Tomtom Amazon

Google Microsoft

Topics

Hints open one at a time

Hint 1

Use doubly Linked list with hashmap of pointers to linked list nodes. add unique number to the linked list. When add is called check if the added number is unique then it have to be added to the linked list and if it is repeated remove it from the linked list if exists. When showFirstUnique is called retrieve the head of the linked list.

Hint 2

Use queue and check that first element of the queue is always unique.

Hint 3

Use set or heap to make running time of each function O(logn).

12:48

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]

Input

["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]

Input

["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]

Your code is saved on this device.Solution