MediumHash TableDesignQueueData Stream

First Unique Number

1 approach, code in every language

You are given a stream of integers and must always be able to report the first value in the stream that has appeared exactly once so far.

Implement the FirstUnique class. The constructor FirstUnique(nums) seeds the stream with an initial array of numbers. The method showFirstUnique() returns the earliest value that is still unique, or -1 when no such value exists. The method add(value) appends value to the stream.

As duplicates arrive, values that were once unique may stop being unique, so the reported answer can change over time.

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]

Start with [2,3,5]; first unique is 2. add(5) makes 5 a duplicate but 2 is still first unique. add(2) makes 2 a duplicate, so 3 becomes first unique. add(3) makes 3 a duplicate, leaving no unique value, so the answer is -1.

Example 2

Input: ["FirstUnique","showFirstUnique","add","add","showFirstUnique"] [[[7,7,7]],[],[7],[8],[]]

Output: [null,-1,null,null,8]

The initial [7,7,7] has no unique value, so the answer is -1. After add(7) and add(8), 8 is the only value seen once, so it becomes the first unique.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^8
1 <= value <= 10^8
At most 5 * 10^4 calls will be made to showFirstUnique and add.

Candidate Queue With Count Map

Hold values in a queue in arrival order and track how many times each has been seen, lazily discarding stale heads.

Loading animation…

Intuition

The first unique value is simply the earliest arrival whose total count is still one, so we preserve arrival order in a queue and keep a count of every value in a hash map. Rather than remove a value from the middle of the queue the moment it becomes a duplicate, we clean up lazily: when asked for the first unique, we pop values off the front as long as their count exceeds one. Whatever remains at the front is the answer, and if the queue empties we return -1. Because every value is enqueued once and dequeued at most once, the amortized cost stays low even across many queries.

Algorithm walkthrough

1In the constructor, create an empty queue and an empty count map, then feed each seed number through add.
2In add(value), increment the count for value in the map and push value onto the back of the queue.
3In showFirstUnique, while the queue is non-empty and the front value's count is greater than one, pop it from the front.
4If the queue still has a front value, return it; otherwise return -1.
5The lazy popping guarantees the front is always a genuinely unique value whenever one exists.

Implementation

from collections import deque, defaultdict
from typing import List

class FirstUnique:
    def __init__(self, nums: List[int]):
        self.queue = deque()
        self.count = defaultdict(int)
        for num in nums:
            self.add(num)

    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] += 1
        self.queue.append(value)

Time

O(1) amortized per call

Space

O(n)

Each value is enqueued once and skipped over the front at most once, so showFirstUnique is amortized constant. The map and queue grow with the number of distinct and total values respectively.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free