Code Implementation

from collections import deque, Counter

class FirstUnique:
    def __init__(self, nums):
        self.queue = deque()
        self.counts = Counter()
        for num in nums:
            self.add(num)

    def showFirstUnique(self):
        while self.queue and self.counts[self.queue[0]] > 1:
            self.queue.popleft()
        return self.queue[0] if self.queue else -1

    def add(self, value):
        self.counts[value] += 1
        if self.counts[value] == 1:
            self.queue.append(value)
      

class FirstUnique {
    unordered_map<int, int> counts;
    queue<int> q;
public:
    FirstUnique(vector<int>& nums) {
        for (int num : nums) {
            add(num);
        }
    }
    
    int showFirstUnique() {
        while (!q.empty() && counts[q.front()] > 1) {
            q.pop();
        }
        return q.empty() ? -1 : q.front();
    }
    
    void add(int value) {
        counts[value]++;
        if (counts[value] == 1) {
            q.push(value);
        }
    }
};
      

import java.util.*;

class FirstUnique {
    private Map<Integer, Integer> counts;
    private Queue<Integer> queue;

    public FirstUnique(int[] nums) {
        counts = new HashMap<>();
        queue = new LinkedList<>();
        for (int num : nums) {
            add(num);
        }
    }

    public int showFirstUnique() {
        while (!queue.isEmpty() && counts.get(queue.peek()) > 1) {
            queue.poll();
        }
        return queue.isEmpty() ? -1 : queue.peek();
    }

    public void add(int value) {
        counts.put(value, counts.getOrDefault(value, 0) + 1);
        if (counts.get(value) == 1) {
            queue.offer(value);
        }
    }
}
      

class FirstUnique {
    constructor(nums) {
        this.counts = new Map();
        this.queue = [];
        for (const num of nums) {
            this.add(num);
        }
    }
    
    showFirstUnique() {
        while (this.queue.length > 0 && this.counts.get(this.queue[0]) > 1) {
            this.queue.shift();
        }
        return this.queue.length === 0 ? -1 : this.queue[0];
    }
    
    add(value) {
        this.counts.set(value, (this.counts.get(value) || 0) + 1);
        if (this.counts.get(value) === 1) {
            this.queue.push(value);
        }
    }
}
      

Problem Description

The First Unique Number problem asks you to design a class that takes a list of integers nums and supports the following operations:

• showFirstUnique(): Returns the first unique integer in the current sequence (i.e., the first integer that occurs exactly once). If there is no such integer, return -1.
• add(value): Adds the integer value to the sequence.

You are required to maintain the order of numbers as they are added, and efficiently determine the first unique number at any time. The input guarantees that each number is an integer, and you must not reuse or skip elements.

Thought Process

At first glance, you might think to check for uniqueness by scanning through the sequence each time showFirstUnique() is called. However, this would be very inefficient, especially if the list is long or if there are many operations.

To optimize, we need a way to quickly:

• Know how many times each number has appeared (to check if it's unique).
• Maintain the order in which numbers are added (to find the first unique efficiently).

This suggests using a hash map (or dictionary) for counting occurrences, and a queue to keep track of the insertion order of unique candidates.

The main trick is to only keep track of numbers that are still potentially unique in our queue, and skip over numbers that have become duplicates as we process queries.

Solution Approach

To efficiently solve the problem, we use two main data structures:

• Hash Map / Dictionary: Stores the count of each number. This allows us to check in constant time whether a number is unique (appeared once) or not.
• Queue: Maintains the order of numbers as they are added. Each number is added to the queue only when it appears for the first time.

Here is the step-by-step algorithm:

1. During initialization, for each number in nums, call add(num) to process it.
2. add(value):
   • Increment the count of value in the hash map.
   • If this is the first time we've seen value, append it to the queue.
3. showFirstUnique():
   • While the queue is not empty and the count of the number at the front is more than one (i.e., not unique), remove it from the queue.
   • If the queue is empty after this, return -1 (no unique number). Otherwise, return the number at the front of the queue.

This approach ensures that both adding numbers and finding the first unique number are efficient.

Example Walkthrough

Let's walk through an example:

Input: nums = [2,3,5]
Operations:
  showFirstUnique() -> returns 2
  add(5)
  showFirstUnique() -> returns 2
  add(2)
  showFirstUnique() -> returns 3
  add(3)
  showFirstUnique() -> returns -1
  

• Initial state: queue = [2,3,5], counts = {2:1, 3:1, 5:1}
• showFirstUnique(): 2 is at front and unique, so return 2.
• add(5): counts[5]=2, queue unchanged.
• showFirstUnique(): 2 is still unique, return 2.
• add(2): counts[2]=2, queue unchanged.
• showFirstUnique(): 2 is no longer unique, remove from queue. Next is 3, which is unique, so return 3.
• add(3): counts[3]=2.
• showFirstUnique(): 3 is now not unique, remove 3. Next is 5, which is not unique, remove 5. Queue is empty, return -1.

Time and Space Complexity

• Brute-force approach: For each showFirstUnique(), scan the entire list to find the first unique number. This is O(N) per query, where N is the list size.
• Optimized approach:
  • add(value): O(1) time, as updating a hash map and appending to a queue are constant-time operations.
  • showFirstUnique(): Each number is removed from the queue at most once, so across all operations, the total time spent is O(N), making the amortized time per call O(1).
  • Space complexity: O(N) for the hash map and O(N) for the queue, where N is the number of unique numbers processed.

Summary

The First Unique Number problem is elegantly solved by combining a hash map for counting occurrences and a queue for maintaining order. This design allows us to efficiently add numbers and retrieve the first unique number at any time, using only O(1) amortized time per operation. The key insight is to only keep track of candidates for uniqueness in the queue, and quickly skip over numbers that have become duplicates. This approach is both simple and highly effective for the problem's requirements.