LeetCode 1429 - First Unique Number

LeetCode Problem 1429

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Design, Queue, Data Stream

Solution

Problem Understanding

The problem requires designing a data structure that can efficiently maintain and retrieve the first unique integer in a queue of numbers. You are given an initial list of integers, and after that, the data structure should support two operations efficiently: retrieving the first unique number (showFirstUnique) and adding a new number to the queue (add).

The input nums represents the initial queue of integers, and the integers are within the range [1, 10^8]. The output for showFirstUnique should return the value of the first integer in the queue that occurs exactly once, or -1 if no such number exists. The constraints indicate that nums can be up to 10^5 elements, and there can be up to 50,000 calls to showFirstUnique and add. This means that a naive approach that scans the queue for each query will be too slow. The problem also implicitly guarantees that all inputs are valid integers within the stated range.

Important edge cases include when all numbers are duplicates, when the queue starts empty, or when the first unique number is removed from the front of the queue as duplicates are added.

Approaches

The brute-force approach is to maintain the queue as a list and scan it from the front whenever showFirstUnique is called, checking counts of each number. This works correctly but is inefficient because counting occurrences in the queue for each query results in O(n) time per query, leading to O(n*m) time for m queries, which is not acceptable given the constraints.

The optimal approach leverages a combination of a hash map and a queue. The hash map tracks the frequency of each number, while a doubly-ended queue (deque) maintains the order of numbers that are currently unique. When adding a number, we update its count and either append it to the deque if it becomes unique or remove it if it ceases to be unique. Retrieving the first unique number then becomes an O(1) operation, as it is always at the front of the deque.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n*m)	O(n)	Scan the entire queue for each showFirstUnique call, too slow
Optimal	O(1) amortized per operation	O(n)	Use hashmap for counts and deque for order of unique elements

Algorithm Walkthrough

1. Initialize a hash map count_map to track the frequency of each number and a queue unique_queue to store numbers that are currently unique.
2. During initialization, iterate through the input list nums. For each number, update its count in count_map. If the count becomes 1, append it to unique_queue. If the count exceeds 1, remove it from unique_queue if present.
3. For showFirstUnique, check the front of unique_queue. If it is empty, return -1. Otherwise, return the number at the front.
4. For add(value), increment count_map[value]. If the count becomes 1, append the value to unique_queue. If the count becomes 2 or more, remove it from unique_queue.
5. The queue always maintains the order of numbers that are currently unique, so retrieving the first element is always correct.

This works because unique_queue always contains only numbers that are unique in the entire data stream and maintains insertion order. The front of the queue is guaranteed to be the first unique number at any time.

Python Solution

from collections import deque
from typing import List

class FirstUnique:

    def __init__(self, nums: List[int]):
        self.count_map = {}
        self.unique_queue = deque()
        for num in nums:
            self.add(num)

    def showFirstUnique(self) -> int:
        while self.unique_queue and self.count_map[self.unique_queue[0]] > 1:
            self.unique_queue.popleft()
        return self.unique_queue[0] if self.unique_queue else -1

    def add(self, value: int) -> None:
        self.count_map[value] = self.count_map.get(value, 0) + 1
        if self.count_map[value] == 1:
            self.unique_queue.append(value)

In this implementation, the constructor iterates through the initial list and uses add to initialize both the count map and the queue. showFirstUnique ensures that the front of the queue is always a unique number. The add method updates counts and appends new unique numbers to the queue. The deque ensures O(1) amortized operations for both adding and removing elements from the front.

Go Solution

package main

type FirstUnique struct {
	countMap    map[int]int
	uniqueQueue []int
}

func Constructor(nums []int) FirstUnique {
	fu := FirstUnique{
		countMap:    make(map[int]int),
		uniqueQueue: []int{},
	}
	for _, num := range nums {
		fu.Add(num)
	}
	return fu
}

func (this *FirstUnique) ShowFirstUnique() int {
	for len(this.uniqueQueue) > 0 && this.countMap[this.uniqueQueue[0]] > 1 {
		this.uniqueQueue = this.uniqueQueue[1:]
	}
	if len(this.uniqueQueue) == 0 {
		return -1
	}
	return this.uniqueQueue[0]
}

func (this *FirstUnique) Add(value int) {
	this.countMap[value]++
	if this.countMap[value] == 1 {
		this.uniqueQueue = append(this.uniqueQueue, value)
	}
}

In Go, a slice is used as the queue. Removing from the front is achieved with slice slicing. The map tracks counts, similar to the Python implementation. The semantics of ShowFirstUnique and Add mirror the Python version. Go does not have a built-in deque, so slices with careful slicing are used.

Worked Examples

Example 1: [2,3,5]

Operation	unique_queue	count_map	Output
init	[2,3,5]	{2:1,3:1,5:1}	-
showFirstUnique	[2,3,5]	{2:1,3:1,5:1}	2
add 5	[2,3,5,5]	{2:1,3:1,5:2}	-
showFirstUnique	[2,3]	{2:1,3:1,5:2}	2
add 2	[2,3,2]	{2:2,3:1,5:2}	-
showFirstUnique	[3]	{2:2,3:1,5:2}	3
add 3	[3,3]	{2:2,3:2,5:2}	-
showFirstUnique	[]	{2:2,3:2,5:2}	-1

Example 2: [7,7,7,7,7,7]

Operation	unique_queue	count_map	Output
init	[]	{7:6}	-
showFirstUnique	[]	{7:6}	-1
add 7	[]	{7:7}	-
add 3	[3]	{7:7,3:1}	-
add 3	[]	{7:7,3:2}	-
add 7	[]	{7:8,3:2}	-
add 17	[17]	{7:8,3:2,17:1}	-
showFirstUnique	[17]	{7:8,3:2,17:1}	17

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) amortized per operation	Adding or removing elements from front/back of deque is O(1) amortized, hashmap lookups are O(1)
Space	O(n)	We store counts of each element and a queue of unique elements

The time complexity is amortized O(1) because each element can be added and removed at most once from the deque. Space complexity is O(n) because both the map and queue can grow proportional to the number of unique elements.

Test Cases

# Example tests
obj = FirstUnique([2,3,5])
assert obj.showFirstUnique() == 2  # initial first unique
obj.add(5)
assert obj.showFirstUnique() == 2
obj.add(2)
assert obj.showFirstUnique() == 3
obj.add(3)
assert obj.showFirstUnique() == -1

obj = FirstUnique([7,7,7,7,7,7])
assert obj.showFirstUnique() == -1
obj.add(7)
obj.add(3)
obj.add(3)
obj.add(7)
obj.add(17)
assert obj.showFirstUnique() == 17

obj = FirstUnique([809])
assert obj.showFirstUnique() == 809
obj.add(809)
assert obj.showFirstUnique() == -1

# Boundary tests
obj = FirstUnique([1]*100000)
assert obj.showFirstUnique() == -1
obj = FirstUnique([i for i in range(1, 100001)])
assert obj.show