First Unique Number
First Unique Number is a medium design data structures problem solved with the queue / circular buffer pattern.
The best approach, optimal (queue with lazy removal), runs in O(1) amortized per operation time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan in arrival order) up.
Problem
Build a structure that tracks a stream of integers and can always report the oldest value that has appeared exactly once so far.
Implement the class FirstUnique:
FirstUnique(int[] nums)starts the stream with the values ofnums, in order.int showFirstUnique()returns the earliest-arrived value whose total count in the stream is exactly 1, or-1if there is no such value.void add(int value)appendsvalueto the stream.
Examples
Example 1
- Input
FirstUnique([4, 9, 4, 6]), showFirstUnique(), add(9), showFirstUnique(), add(6), showFirstUnique()- Output
9, 6, -1- Why
- 9 is unique at first; once a second 9 arrives, 6 is the oldest unique value; after a second 6 nothing is unique.
Example 2
- Input
FirstUnique([8, 8]), showFirstUnique(), add(3), add(5), showFirstUnique(), add(3), showFirstUnique()- Output
-1, 3, 5- Why
- The repeated 8 never counts; 3 becomes the answer until it is repeated, then 5 takes over.
Constraints
1 <= nums.length <= 10^51 <= nums[i], value <= 10^8- At most
5 * 10^4calls in total toshowFirstUniqueandadd.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan in arrival order) | O(1) add, O(n) query | O(n) |
| Optimal (queue with lazy removal) | O(1) amortized per operation | O(n) |
1Brute force (scan in arrival order)
O(1) add, O(n) queryEach query may walk the whole history of n values.O(n)The list of all values and the count map.Store every value in arrival order plus a count map. To answer a query, walk the list from the start and return the first value whose count is 1.
- Constructor and
add: append the value to the list and increase its count. showFirstUnique: scan the list; return the first value with count 1, or -1.
class FirstUnique {
private final List<Integer> order = new ArrayList<>();
private final Map<Integer, Integer> count = new HashMap<>();
public FirstUnique(int[] nums) {
for (int x : nums) add(x);
}
public int showFirstUnique() {
for (int x : order) {
if (count.get(x) == 1) return x;
}
return -1;
}
public void add(int value) {
order.add(value);
count.merge(value, 1, Integer::sum);
}
}class FirstUnique:
def __init__(self, nums: List[int]):
self.order = []
self.count = {}
for x in nums:
self.add(x)
def showFirstUnique(self) -> int:
for x in self.order:
if self.count[x] == 1:
return x
return -1
def add(self, value: int) -> None:
self.order.append(value)
self.count[value] = self.count.get(value, 0) + 1class FirstUnique {
vector<int> order;
unordered_map<int, int> count;
public:
FirstUnique(vector<int>& nums) {
for (int x : nums) add(x);
}
int showFirstUnique() {
for (int x : order) {
if (count[x] == 1) return x;
}
return -1;
}
void add(int value) {
order.push_back(value);
count[value]++;
}
};class FirstUnique {
constructor(nums) {
this.order = [];
this.count = new Map();
for (const x of nums) this.add(x);
}
showFirstUnique() {
for (const x of this.order) {
if (this.count.get(x) === 1) return x;
}
return -1;
}
add(value) {
this.order.push(value);
this.count.set(value, (this.count.get(value) || 0) + 1);
}
}2Optimal (queue with lazy removal)
O(1) amortized per operationEach distinct value is pushed once and popped at most once over the whole run.O(n)The count map and the queue hold at most one entry per distinct value.Push a value onto a queue only the first time it is seen, and keep counts in a hash map. On a query, pop from the front while the front value has been repeated; those values can never be the answer again. The front that survives is the answer.
add(value): increase its count; if the count is now 1, push it onto the queue.showFirstUnique: while the queue is not empty and the front's count is greater than 1, pop it.- Return the front, or -1 if the queue is empty.
class FirstUnique {
private final Deque<Integer> queue = new ArrayDeque<>();
private final Map<Integer, Integer> count = new HashMap<>();
public FirstUnique(int[] nums) {
for (int x : nums) add(x);
}
public int showFirstUnique() {
while (!queue.isEmpty() && count.get(queue.peekFirst()) > 1) queue.pollFirst();
return queue.isEmpty() ? -1 : queue.peekFirst();
}
public void add(int value) {
int c = count.merge(value, 1, Integer::sum);
if (c == 1) queue.addLast(value);
}
}class FirstUnique:
def __init__(self, nums: List[int]):
self.queue = deque()
self.count = {}
for x in nums:
self.add(x)
def showFirstUnique(self) -> int:
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, value: int) -> None:
self.count[value] = self.count.get(value, 0) + 1
if self.count[value] == 1:
self.queue.append(value)class FirstUnique {
deque<int> q;
unordered_map<int, int> count;
public:
FirstUnique(vector<int>& nums) {
for (int x : nums) add(x);
}
int showFirstUnique() {
while (!q.empty() && count[q.front()] > 1) q.pop_front();
return q.empty() ? -1 : q.front();
}
void add(int value) {
if (++count[value] == 1) q.push_back(value);
}
};class FirstUnique {
constructor(nums) {
this.queue = [];
this.head = 0;
this.count = new Map();
for (const x of nums) this.add(x);
}
showFirstUnique() {
while (this.head < this.queue.length && this.count.get(this.queue[this.head]) > 1) this.head++;
return this.head < this.queue.length ? this.queue[this.head] : -1;
}
add(value) {
const c = (this.count.get(value) || 0) + 1;
this.count.set(value, c);
if (c === 1) this.queue.push(value);
}
}Edge cases to test
- Every initial value is repeated, so the first answer is -1
- A value that appears a third time must not become unique again
- Adding a brand-new value when nothing is unique makes it the answer
- Many queries in a row with no additions in between
Hints
Hint 1
Keep a count of how many times each value has appeared; a value is unique exactly when its count is 1.
Hint 2
Scanning all values on every query is too slow. Keep the values in arrival order and only look at the front.
Hint 3
Values at the front of a queue that are no longer unique can be thrown away for good, because a value that has been repeated can never become unique again.
FAQ
What is the best time complexity for First Unique Number?
Optimal (queue with lazy removal) runs in O(1) amortized per operation time and O(n) extra space. Each distinct value is pushed once and popped at most once over the whole run.
Which pattern does First Unique Number use?
It is a design data structures problem that uses the queue / circular buffer pattern. Other problems with the same pattern: Design Hit Counter, Design Circular Queue, Design Snake Game.
Is there a brute force solution for First Unique Number?
Yes. Brute force (scan in arrival order) takes O(1) add, O(n) query time and O(n) space. Store every value in arrival order plus a count map.
Which edge cases should I test for First Unique Number?
Every initial value is repeated, so the first answer is -1; A value that appears a third time must not become unique again; Adding a brand-new value when nothing is unique makes it the answer; Many queries in a row with no additions in between.