First Unique Number

Problem Statement

Design a data structure that receives a stream of integers and can return the first unique (non-repeating) integer at any point. Implement the FirstUnique class:

• FirstUnique(nums) — Initialize with an array of integers.
• showFirstUnique() — Return the first unique integer. If none exists, return -1.
• add(value) — Add a new integer to the stream.

Example:

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:
- Init with [2, 3, 5] → first unique = 2
- Add 5 → 5 is now duplicate, first unique still 2
- Add 2 → 2 is now duplicate, first unique = 3
- Add 3 → 3 is now duplicate, no unique left → -1

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= value <= 10^8
• At most 5 * 10^4 calls to showFirstUnique and add.

Difficulty: Medium (LC 1429)

---

Pattern Recognition

• What is the input structure? A stream of integers with two operations: add and query.
• What are we optimizing? O(1) retrieval of the first unique element, and O(1) addition.
• What pattern does this fit? HashMap + Doubly Linked List (or OrderedDict in Python). The HashMap tracks counts, and the linked list maintains insertion order with O(1) removal.
• Why does this pattern fit? You need to maintain order (for "first") and quickly remove elements when they become duplicates. A doubly linked list allows O(1) removal given a reference to the node. The HashMap provides O(1) lookup to find that reference.

---

Approach

Brute Force — Array + HashMap

Store all numbers in a list. For showFirstUnique, scan the list and check counts.

class FirstUnique:
    def __init__(nums): store nums, count occurrences
    def showFirstUnique():
        for num in list:
            if count[num] == 1: return num
        return -1
    def add(val): append, increment count

Time: add is O(1), showFirstUnique is O(n). Space: O(n). Why insufficient: With up to 50,000 showFirstUnique calls and 100,000 elements, worst case is 5 * 10^9 operations.

Optimal — HashMap + OrderedDict (or Doubly Linked List)

Key Insight: Use an OrderedDict (Python) to maintain unique elements in insertion order. When an element becomes a duplicate, remove it from the OrderedDict in O(1). The first element in the OrderedDict is always the first unique.

Step-by-step:

1. Maintain a count dictionary and an OrderedDict of unique elements.
2. add(val):
   • Increment count[val].
   • If count[val] == 1, add to OrderedDict.
   • If count[val] == 2, remove from OrderedDict (it is no longer unique).
   • If count[val] > 2, do nothing (already removed).
3. showFirstUnique():
   • Return the first key of the OrderedDict if non-empty, else -1.
4. __init__: call add for each element in the initial array.

class FirstUnique:
    init(nums):
        uniques = OrderedDict()
        count = defaultdict(int)
        for num in nums: add(num)

    showFirstUnique():
        return first key of uniques, or -1

    add(val):
        count[val] += 1
        if count[val] == 1: uniques[val] = True
        elif count[val] == 2: del uniques[val]

Time: add is O(1), showFirstUnique is O(1). Space: O(n) for the HashMap and OrderedDict.

---

Walkthrough

Init: nums = [2, 3, 5]

Operation	count	OrderedDict (uniques)	First unique
add(2)			2
add(3)			2
add(5)			2
showFirstUnique()	—	—	2
add(5)		{2, 3} (removed 5)	2
showFirstUnique()	—	—	2
add(2)		{3} (removed 2)	3
showFirstUnique()	—	—	3
add(3)		{} (removed 3)	-1
showFirstUnique()	—	—	-1

---

Implementation

TypeScript

class FirstUnique {
    private count: Map<number, number>;
    // Map maintains insertion order in JS/TS
    private uniques: Map<number, boolean>;

    constructor(nums: number[]) {
        this.count = new Map();
        this.uniques = new Map();

        for (const num of nums) {
            this.add(num);
        }
    }

    showFirstUnique(): number {
        // Map iterator gives keys in insertion order
        const first = this.uniques.keys().next();
        return first.done ? -1 : first.value;
    }

    add(value: number): void {
        const cnt = (this.count.get(value) ?? 0) + 1;
        this.count.set(value, cnt);

        if (cnt === 1) {
            // First occurrence — add to uniques
            this.uniques.set(value, true);
        } else if (cnt === 2) {
            // Second occurrence — no longer unique, remove
            this.uniques.delete(value);
        }
        // count > 2: already removed, nothing to do
    }
}

C++

class FirstUnique {
    unordered_map<int, int> count;
    // Use a linked list to maintain insertion order of unique elements
    list<int> uniques;
    unordered_map<int, list<int>::iterator> pos; // value → iterator for O(1) removal

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

    int showFirstUnique() {
        return uniques.empty() ? -1 : uniques.front();
    }

    void add(int value) {
        count[value]++;

        if (count[value] == 1) {
            // First occurrence — add to uniques
            uniques.push_back(value);
            pos[value] = prev(uniques.end());
        } else if (count[value] == 2) {
            // Second occurrence — no longer unique, remove in O(1)
            uniques.erase(pos[value]);
            pos.erase(value);
        }
        // count > 2: already removed, nothing to do
    }
};

Alternative — Explicit Doubly Linked List (shows understanding):

TypeScript

class DLLNode {
    val: number;
    prev: DLLNode | null = null;
    next: DLLNode | null = null;

    constructor(val: number) {
        this.val = val;
    }
}

class FirstUniqueLinkedList {
    private count: Map<number, number> = new Map();
    private nodeMap: Map<number, DLLNode> = new Map(); // val → DLLNode for O(1) removal
    private head: DLLNode; // sentinel
    private tail: DLLNode; // sentinel

    constructor(nums: number[]) {
        this.head = new DLLNode(-1);
        this.tail = new DLLNode(-1);
        this.head.next = this.tail;
        this.tail.prev = this.head;

        for (const num of nums) {
            this.add(num);
        }
    }

    private remove(node: DLLNode): void {
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
    }

    private append(node: DLLNode): void {
        // Insert before tail sentinel
        node.prev = this.tail.prev;
        node.next = this.tail;
        this.tail.prev!.next = node;
        this.tail.prev = node;
    }

    showFirstUnique(): number {
        if (this.head.next === this.tail) return -1;
        return this.head.next!.val;
    }

    add(value: number): void {
        const cnt = (this.count.get(value) ?? 0) + 1;
        this.count.set(value, cnt);

        if (cnt === 1) {
            const node = new DLLNode(value);
            this.nodeMap.set(value, node);
            this.append(node);
        } else if (cnt === 2) {
            const node = this.nodeMap.get(value)!;
            this.nodeMap.delete(value);
            this.remove(node);
        }
    }
}

C++

struct DLLNode {
    int val;
    DLLNode* prev = nullptr;
    DLLNode* next = nullptr;
    DLLNode(int v) : val(v) {}
};

class FirstUniqueLinkedList {
    unordered_map<int, int> count;
    unordered_map<int, DLLNode*> nodeMap; // val → DLLNode* for O(1) removal
    DLLNode* head; // sentinel
    DLLNode* tail; // sentinel

    void removeNode(DLLNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void appendNode(DLLNode* node) {
        // Insert before tail sentinel
        node->prev = tail->prev;
        node->next = tail;
        tail->prev->next = node;
        tail->prev = node;
    }

public:
    FirstUniqueLinkedList(vector<int>& nums) {
        head = new DLLNode(-1);
        tail = new DLLNode(-1);
        head->next = tail;
        tail->prev = head;

        for (int num : nums) {
            add(num);
        }
    }

    int showFirstUnique() {
        if (head->next == tail) return -1;
        return head->next->val;
    }

    void add(int value) {
        count[value]++;

        if (count[value] == 1) {
            DLLNode* node = new DLLNode(value);
            nodeMap[value] = node;
            appendNode(node);
        } else if (count[value] == 2) {
            DLLNode* node = nodeMap[value];
            nodeMap.erase(value);
            removeNode(node);
            delete node;
        }
    }
};

Watch out:

1. Using a regular dict instead of OrderedDict. In Python 3.7+, regular dicts maintain insertion order. However, using OrderedDict makes the intent explicit and is safer for interviews. If the interviewer asks, mention that CPython dicts are insertion-ordered since 3.7.
2. Deleting from OrderedDict for count >= 3. Only delete when count == 2 (the transition from unique to duplicate). For count > 2, the key is already gone from the OrderedDict. Attempting to delete again raises a KeyError.
3. showFirstUnique scanning the entire OrderedDict. Use next(iter(self.uniques)) for O(1). Do not iterate through the OrderedDict to find the first element.

---

Complexity Analysis

	showFirstUnique	add	Space
Brute Force	O(n)	O(1)	O(n)
OrderedDict	O(1)	O(1) amortized	O(n)
Doubly Linked List	O(1)	O(1)	O(n)

Bottleneck: The space is O(n) regardless — you must track all seen elements to know if a new addition is a duplicate. The OrderedDict/DLL approach achieves O(1) for both operations by trading space for the ordered structure.

---

Edge Cases

1. All elements are the same — showFirstUnique returns the element after init (count=1), then -1 after any duplicate is added.
2. No duplicates — showFirstUnique always returns the first element.
3. Init with empty array — showFirstUnique returns -1 until add is called.
4. Adding the first unique element again — It transitions from unique to duplicate. The next unique takes over.
5. Single element — First unique is that element. Adding it again makes it -1.
6. Large stream (10^5 elements) — O(1) operations ensure performance.

---

Related Problems

• LC 387 — First Unique Character in a String — Static version: find the first non-repeating character. HashMap + single scan.
• LC 146 — LRU Cache — Same HashMap + DLL pattern, but for least recently used eviction.
• LC 460 — LFU Cache — More complex: HashMap + multiple DLLs organized by frequency.
• LC 895 — Maximum Frequency Stack — HashMap + stack per frequency. Related data structure design.

---

What is Expected at Each Level

Junior: Implement the brute-force approach with HashMap for counts and linear scan for showFirstUnique. Recognize that O(n) per query is suboptimal.

Mid-level: Use OrderedDict for O(1) operations. Explain why insertion order matters and how deletion from OrderedDict works. Handle all edge cases.

Senior: Implement the doubly linked list version from scratch (shows deep understanding of the LRU Cache pattern). Discuss thread-safety for concurrent streams (locks on add/show). Extend to: "What if you need the k-th unique number?" (Skip list or indexed DLL). Connect to real-world systems like unique visitor tracking.