First Unique Number

Medium · Arrays & Hashing · Explanation and code example

LinkedHashSet for Queue, and HashMap of Unique-Statuses

How it works

Instead of lazily removing non-unique elements during showFirstUnique(), we can eagerly remove them when they become non-unique. Using a LinkedHashSet (or OrderedDict) allows O(1) removal by value while preserving insertion order. This makes showFirstUnique() a true O(1) operation.

Steps

  1. Constructor: For each number in the initial array, call add().
  2. add(value):
    • If the value is new, mark it as unique in the hash map and add it to the set.
    • If seen once before (currently unique), mark it as non-unique and remove it from the set.
    • If already non-unique, do nothing.
  3. showFirstUnique(): Return the first element from the set if non-empty, otherwise return -1.

Complexity

  • Time complexity:

    • constructor: O(K)

    • add(): O(1)

    • showFirstUnique(): O(1)

  • Space complexity: O(N)

Where K is the length of the initial array passed into the constructor and N is the total number of items added into the queue so far (including those from the constructor).

Things to watch for

Adding Initial Numbers Twice to the Queue

In approaches that use both a queue and a hash map, calling add() for initial numbers while also directly pushing them to the queue results in duplicates. Either iterate through the initial array and call add() for each element (which handles both structures), or manually handle both structures without calling add(). Mixing both approaches corrupts the data structure.

Not Cleaning Stale Non-Unique Elements from the Queue

When lazily removing non-unique elements, the queue may contain stale entries that are no longer unique. Failing to pop these entries before returning the front element causes showFirstUnique() to return a non-unique number. Always check the hash map status and remove invalidated entries from the front before returning.

Modifying Uniqueness Status Incorrectly on Duplicate Adds

When a number is added for the third or subsequent time, its uniqueness status should remain false. A common bug is toggling the status back to true or re-adding it to the queue. The hash map should transition from "not seen" to "unique" to "non-unique" and never go back.

Python code example

from typing import List
from collections import OrderedDict

# In Python, we have to make do with the OrderedDict class. We can use it as a Set by setting
# the values to None.

class FirstUnique:

    def __init__(self, nums: List[int]):
        self._queue = OrderedDict()
        self._is_unique = {}

        for num in nums:
            # Notice that we're calling the "add" method of FirstUnique; not of the queue.
            self.add(num)

    def showFirstUnique(self) -> int:
        # Check if there is still a value left in the queue. There might be no uniques.
        if self._queue:
            # We don't want to actually *remove* the value.
            # Seeing as OrderedDict has no "get first" method, the way that we can get
            # the first value is to create an iterator, and then get the "next" value
            # from that. Note that this is O(1).
            return next(iter(self._queue))

        return -1

    def add(self, value: int) -> None:
        # Case 1: We need to add the number to the queue and mark it as unique.
        if value not in self._is_unique:
            self._is_unique[value] = True
            self._queue[value] = None

        # Case 2: We need to mark the value as no longer unique and then
        # remove it from the queue.
        elif self._is_unique[value]:
            self._is_unique[value] = False
            self._queue.pop(value)

        # Case 3: We don't need to do anything; the number was removed from the queue
        # the second time it occurred.

C++ code example

class FirstUnique {
private:
    std::list<int> setQueue;
    std::unordered_map<int, std::list<int>::iterator> queuePosition;
    std::unordered_map<int, bool> isUnique;

public:
    FirstUnique(vector<int>& nums) {
        for (int num : nums) {
            this->add(num);
        }
    }

    int showFirstUnique() {
        // If the queue contains values, we need to get the first one from it.
        // We can do this by making an iterator, and getting its first item.
        if (!setQueue.empty()) {
            return setQueue.front();
        }
        return -1;
    }

    void add(int value) {
        // Case 1: This value is not yet in the data structure.
        // It should be ADDED.
        if (isUnique.find(value) == isUnique.end()) {
            isUnique[value] = true;
            setQueue.push_back(value);
            queuePosition[value] = std::prev(setQueue.end());
        // Case 2: This value has been seen once, so is now becoming
        // non-unique. It should be REMOVED.
        } else if (isUnique[value]) {
            isUnique[value] = false;
            setQueue.erase(queuePosition[value]);
            queuePosition.erase(value);
        }
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations