NeetCode #30LC-1429MediumArrays & HashingNC Algo100
← Back to All Problems#30 · #1429 · First Unique Number(第一个唯一数字)
📌 Problem Statement & Constraints
Design a class that supports adding numbers to a stream and returning the first unique (non-repeating) number. Implement
showFirstUnique() and add(value). If no unique number exists, return -1. Constraints: 1 <= nums.length <= 10^5, 1 <= value <= 10^8; at most 5 * 10^4 calls to add.💡 Core Algorithmic Approaches
- Two data structures are needed: a frequency map to know which values are unique, and a queue to preserve the order in which values were added.
showFirstUnique()pops from the front of the queue while the front value's count exceeds 1, then returns the front (or-1if the queue is empty).- The lazy eviction is what makes the total cost linear: each value is removed from the queue at most once across all calls.
add(value)increments the count, and enqueues the value only when its count becomes exactly 1 (i.e. the first time it is seen).
💻 Benchmark Python3 Implementation
class FirstUnique:
def __init__(self, nums: List[int]):
from collections import Counter, deque
self.cnt = Counter(nums)
self.q = deque(nums) # preserves insertion order
def showFirstUnique(self) -> int:
# lazily drop values that are no longer unique
while self.q and self.cnt[self.q[0]] > 1:
self.q.popleft()
return self.q[0] if self.q else -1
def add(self, value: int) -> None:
self.cnt[value] += 1
if self.cnt[value] == 1: # first time seen -> candidate
self.q.append(value)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) amortised per operation. showFirstUnique may pop several values, but each value is popped at most once over the object's lifetime, so the total work across all calls is O(total operations).
💾 Space Complexity
O(n) for the counter and the queue.
⚠️ Interview Pitfalls & Follow-ups
- Rebuilding the queue on every
showFirstUnique: O(n) per call, giving O(n * calls) overall. The lazy-eviction loop is what keeps it linear. - Enqueuing on every
add: duplicates would flood the queue and require filtering; only enqueue when the count becomes 1. - Deleting the queue entry when a value becomes a duplicate: you cannot remove from the middle of a deque in O(1); lazy eviction at the front is the correct approach.
- Returning
Noneinstead of-1: the contract requires-1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.