First Unique Number - Leetcode Solution

Problem Statement: You have a queue of integers, you need to retrieve the first unique integer in the queue. Implement the FirstUnique class: • FirstUnique(int[] nums) Initializes the object with the numbers in the queue. • int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer. • void add(int value) insert value to the queue.

Solution: To solve this problem, we can use a hash map to keep track of each number's frequency in the queue. We can also use a doubly linked list to keep track of the order of unique numbers in the queue.

When adding a new number to the queue, we check if the number is already in the hash map. If it is, we simply increase its frequency. If it is not, we add it to the hash map with a frequency of 1 and add it to the end of the linked list.

When showing the first unique number in the queue, we simply check if the head of the linked list has a frequency of 1. If it does, we return its value. Otherwise, we remove the head of the linked list and keep checking until we find a unique number or the list is empty.

Here is the code implementation for the First Unique Number problem on LeetCode:

public class FirstUnique {

Map<Integer, Integer> frequencyMap;
Deque<Integer> uniqueQueue;

public FirstUnique(int[] nums) {
    frequencyMap = new HashMap<>();
    uniqueQueue = new LinkedList<>();

    for (int num : nums) {
        add(num);
    }
}

public int showFirstUnique() {
    while (!uniqueQueue.isEmpty() && frequencyMap.get(uniqueQueue.peek()) > 1) {
        uniqueQueue.poll();
    }

    if (!uniqueQueue.isEmpty()) {
        return uniqueQueue.peek();
    }

    return -1;
}

public void add(int value) {
    if (frequencyMap.containsKey(value)) {
        frequencyMap.put(value, frequencyMap.get(value) + 1);
    } else {
        frequencyMap.put(value, 1);
        uniqueQueue.offer(value);
    }
}

}

Time Complexity: • Initialization: O(n) • showFirstUnique: O(1) (amortized) • add: O(1)

Space Complexity: O(n)

Note: The time complexity of showFirstUnique() method is O(1) on average, but can be O(n) in the worst case when all elements in the queue have a frequency of 2. To avoid this worst case scenario, we remove all elements from the head of the uniqueQueue that have a frequency greater than 1.

1