Solution Explanation and Code

This problem requires designing a data structure that efficiently retrieves the first unique number from a stream of integers. The solution uses a combination of a hash map (or dictionary) and a queue (or deque).

Approach:

The core idea is to maintain two data structures:

1. Count Map (HashMap/Dictionary): This stores the frequency of each number encountered in the stream. It allows for O(1) lookup of the count of a number.

2. Queue (Queue/Deque): This stores the numbers in the order they appear in the stream. It's crucial for maintaining the order to find the first unique number.

The showFirstUnique() method iterates through the queue, removing elements that are not unique (count > 1) until it finds the first unique number or the queue is empty. The add() method updates the count map and adds the new number to the queue.

Time and Space Complexity Analysis:

• Time Complexity:

  • __init__ (constructor): O(N) to initialize the count map and queue, where N is the length of the input array.
  • showFirstUnique(): In the worst case, it iterates through the entire queue, which is O(N) in the worst case, but is amortized to O(1) because in most calls it'll find the unique element early
  • add(): O(1) - adding to the queue and updating the count map are constant time operations.

• Space Complexity: O(N) to store the count map and the queue. In the worst case, all numbers are unique.

Code Implementations:

The provided code implements the above approach in several languages. I'll focus on the Python and Java versions, highlighting key parts:

Python3 (Solution 1):

from collections import Counter, OrderedDict
from collections import deque
class FirstUnique:
    def __init__(self, nums: List[int]):
        self.cnt = Counter(nums) #Efficient count of elements
        self.unique = OrderedDict({v: 1 for v in nums if self.cnt[v] == 1}) #OrderedDict maintains insertion order
 
    def showFirstUnique(self) -> int:
        return -1 if not self.unique else next(iter(self.unique)) #Returns the first key of OrderedDict
 
    def add(self, value: int) -> None:
        self.cnt[value] += 1
        if self.cnt[value] == 1:
            self.unique[value] = 1
        elif value in self.unique:
            del self.unique[value] #Remove if no longer unique
 
 

Java (Solution 1):

import java.util.*;
 
class FirstUnique {
    private Map<Integer, Integer> cnt = new HashMap<>(); //HashMap for efficient counting
    private Set<Integer> unique = new LinkedHashSet<>(); //LinkedHashSet maintains insertion order
 
    public FirstUnique(int[] nums) {
        for (int v : nums) {
            cnt.put(v, cnt.getOrDefault(v, 0) + 1);
        }
        for (int v : nums) {
            if (cnt.get(v) == 1) {
                unique.add(v);
            }
        }
    }
 
    public int showFirstUnique() {
        return unique.isEmpty() ? -1 : unique.iterator().next(); //Returns first element from set
    }
 
    public void add(int value) {
        cnt.put(value, cnt.getOrDefault(value, 0) + 1);
        if (cnt.get(value) == 1) {
            unique.add(value);
        } else {
            unique.remove(value);
        }
    }
}

Python3 (Solution 2): This solution uses a deque instead of OrderedDict for better performance in some cases.

from collections import Counter, deque
class FirstUnique:
    def __init__(self, nums: List[int]):
        self.cnt = Counter(nums)
        self.q = deque(nums)
 
    def showFirstUnique(self) -> int:
        while self.q and self.cnt[self.q[0]] != 1:
            self.q.popleft()
        return -1 if not self.q else self.q[0]
 
    def add(self, value: int) -> None:
        self.cnt[value] += 1
        self.q.append(value)

The C++ and Go solutions follow similar principles, utilizing unordered_map (C++) or map (Go) for counting and deque (C++ and Go) for maintaining order. The key is the combination of a fast count mechanism and a queue to track order. Solution 2 is generally faster because deque operations (popleft, append) are slightly faster than OrderedDict's next iterator in Python or LinkedHashSet's iteration in Java.