Problem Statement
You are given a queue of numbers, and you need to find the first unique number in the queue at any given time.
You must also support two operations:

1. showFirstUnique() → returns the first unique (non-repeated) number in the queue, or -1 if none exists.
2. add(value) → adds a new number to the queue.

The goal is to design an efficient data structure to handle both operations quickly.

Example
Input:

FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // returns 2
firstUnique.add(5);
firstUnique.showFirstUnique(); // returns 2
firstUnique.add(2);
firstUnique.showFirstUnique(); // returns 3
firstUnique.add(3);
firstUnique.showFirstUnique(); // returns -1

Output:

2
2
3
-1

---

Understanding the Problem

We need to track numbers in the order they arrive and efficiently determine the first number that occurs exactly once.

The challenge comes from two things:

1. We must maintain insertion order (like a queue).
2. We must also know how many times each number has appeared.

If we try to check every time by scanning the entire list, it would be slow — O(n) for each query.
We need something much faster, ideally close to O(1) per operation.

---

Thinking Process and Approach

We can break the problem into two parts:

1. Tracking frequency of numbers
   We can use a HashMap<Integer, Integer> to count how many times each number appears.
2. Tracking order of unique numbers
   To keep track of numbers that have appeared only once and maintain order, we can use a Queue (like LinkedList).

When a number is added:

• Increment its frequency in the map.
• If it’s the first occurrence, add it to the queue.
• If it appears again, we don’t remove it immediately from the queue but skip it later during retrieval.

When we call showFirstUnique():

• We check the front of the queue.
• If the number at the front is no longer unique (frequency > 1), remove it and check the next.
• The first remaining number with frequency 1 is the answer.
• If none are unique, return -1.

---

Step-by-Step Example

Let’s simulate the example step by step:

Start with nums = [2, 3, 5]
Queue: [2, 3, 5]
Map: {2:1, 3:1, 5:1}

1. showFirstUnique() → queue front is 2 → frequency = 1 → output 2
2. add(5) → now 5 appears twice → {2:1, 3:1, 5:2}
   Queue: [2, 3, 5]
showFirstUnique() → 2 still valid → output 2
3. add(2) → {2:2, 3:1, 5:2}
showFirstUnique() → 2 invalid (freq=2) → move to 3 → output 3
4. add(3) → {2:2, 3:2, 5:2}
   Now all have frequency > 1
   showFirstUnique() → output -1

---

Java Code Implementation

import java.util.*;

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

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

    public int showFirstUnique() {
        // Remove elements from the front that are no longer unique
        while (!queue.isEmpty() && countMap.get(queue.peek()) > 1) {
            queue.poll();
        }
        return queue.isEmpty() ? -1 : queue.peek();
    }

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

    public static void main(String[] args) {
        FirstUnique firstUnique = new FirstUnique(new int[]{2, 3, 5});
        System.out.println(firstUnique.showFirstUnique()); // 2
        firstUnique.add(5);
        System.out.println(firstUnique.showFirstUnique()); // 2
        firstUnique.add(2);
        System.out.println(firstUnique.showFirstUnique()); // 3
        firstUnique.add(3);
        System.out.println(firstUnique.showFirstUnique()); // -1
    }
}

---

Thinking Behind the Code

1. The countMap keeps track of how many times each number appears.
2. The queue maintains the order of insertion.
3. When adding a number:
   • If it’s new (first occurrence), add it to both structures.
   • If it’s repeating, only update the count.
4. When fetching the first unique number:
   • Continuously check the queue’s front until a valid unique number appears.
   • If the queue becomes empty, return -1.

This ensures both operations are efficient.

---

Time and Space Complexity

• Time Complexity:
  • add() → O(1)
  • showFirstUnique() → Amortized O(1) because each number is added and removed at most once.
• Space Complexity: O(n)
  We store each number’s frequency and maintain a queue of numbers.

---

Key Takeaways

1. The problem teaches how to combine HashMap and Queue to maintain order while tracking frequency.
2. The trick is to delay removing duplicates from the queue — we simply skip them when checking.
3. This pattern of using a hash map plus a queue is common in streaming problems like:
   • First non-repeating character in a stream.
   • Cache or rate-limiting algorithms.
4. Always ensure that updates and lookups are efficient when dealing with repeated additions and queries.