First Unique Number

Medium Design Data Structures Queue / Circular Buffer Original on LeetCode

Reported atUber

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 of nums, in order.
  • int showFirstUnique() returns the earliest-arrived value whose total count in the stream is exactly 1, or -1 if there is no such value.
  • void add(int value) appends value to 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^5
  • 1 <= nums[i], value <= 10^8
  • At most 5 * 10^4 calls in total to showFirstUnique and add.

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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (scan in arrival order)O(1) add, O(n) queryO(n)
Optimal (queue with lazy removal)O(1) amortized per operationO(n)

1Brute force (scan in arrival order)

TimeO(1) add, O(n) queryEach query may walk the whole history of n values.
SpaceO(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.

  1. Constructor and add: append the value to the list and increase its count.
  2. 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);
    }
}

2Optimal (queue with lazy removal)

TimeO(1) amortized per operationEach distinct value is pushed once and popped at most once over the whole run.
SpaceO(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.

  1. add(value): increase its count; if the count is now 1, push it onto the queue.
  2. showFirstUnique: while the queue is not empty and the front's count is greater than 1, pop it.
  3. 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);
    }
}

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.