Problem Description

You need to design a data structure that maintains a queue of integers and can efficiently identify the first unique (non-duplicate) integer in the queue.

The FirstUnique class should support three operations:

1. Constructor FirstUnique(int[] nums): Initialize the data structure with an initial array of integers. These integers form the starting queue.

2. Method showFirstUnique(): Return the value of the first unique integer in the queue. A unique integer is one that appears exactly once in the entire queue. If no unique integer exists, return -1. The "first" unique integer refers to the one that appears earliest in the queue order.

3. Method add(int value): Add a new integer to the end of the queue. This may affect which integers are considered unique.

Key Points:

• The queue maintains insertion order - elements added first appear before elements added later
• An integer is unique if it appears exactly once in the entire queue
• When showFirstUnique() is called, you need to find the earliest-positioned integer that appears only once
• Adding a duplicate of a previously unique integer makes it non-unique
• The data structure needs to efficiently track both the count of each integer and maintain the order of unique integers

Example Scenario:

• If the queue contains [2, 3, 5, 3], the first unique integer is 2 (appears once and is first among unique values)
• After adding 2 to make it [2, 3, 5, 3, 2], the first unique integer becomes 5 (since 2 now appears twice)
• If all integers appear more than once, showFirstUnique() returns -1

Intuition

To find the first unique integer efficiently, we need to track two things: how many times each integer appears, and the order of unique integers.

The naive approach would be to iterate through the entire queue each time showFirstUnique() is called, counting occurrences and finding the first unique value. However, this would be inefficient with O(n) time for each query.

The key insight is to separate the tracking of counts from the tracking of unique values. We can maintain:

1. A frequency counter to know how many times each integer appears
2. A separate collection that only stores unique integers in their order of appearance

When we think about maintaining order for unique integers, we need a data structure that preserves insertion order and allows efficient removal when an integer becomes non-unique. An OrderedDict is perfect for this - it maintains insertion order and supports O(1) removal.

Here's the clever part: when an integer's count changes, we only need to update the unique collection in two cases:

• When count goes from 0 to 1: The integer becomes unique, so add it to our ordered unique collection
• When count goes from 1 to 2: The integer is no longer unique, so remove it from our unique collection

By maintaining these two data structures, showFirstUnique() becomes an O(1) operation - we just return the first key in our ordered unique collection. The add() operation is also O(1) since we're only updating a counter and potentially adding/removing from the OrderedDict.

This approach trades space for time efficiency - we store additional data structures but gain constant-time operations for our queries.

Learn more about Queue and Data Stream patterns.

Solution Approach

The solution uses two main data structures to efficiently track unique integers:

1. Counter (self.cnt): A hash map that stores the frequency count of each integer in the queue
2. OrderedDict (self.unique): An ordered dictionary that maintains only the unique integers in their order of appearance

Let's walk through the implementation:

Constructor: __init__(self, nums)

def __init__(self, nums: List[int]):
    self.cnt = Counter(nums)
    self.unique = OrderedDict({v: 1 for v in nums if self.cnt[v] == 1})

• First, create a Counter from the input array to get the frequency of each integer
• Then, build an OrderedDict containing only the integers that appear exactly once
• The OrderedDict comprehension iterates through nums (preserving original order) and includes only values where self.cnt[v] == 1
• The value 1 in the OrderedDict is just a placeholder - we only care about the keys and their order

Query Method: showFirstUnique()

def showFirstUnique(self) -> int:
    return -1 if not self.unique else next(v for v in self.unique.keys())

• If the unique OrderedDict is empty, return -1
• Otherwise, return the first key in the OrderedDict using next() on the keys iterator
• This is O(1) since we're just accessing the first element

Update Method: add(value)

def add(self, value: int) -> None:
    self.cnt[value] += 1
    if self.cnt[value] == 1:
        self.unique[value] = 1
    elif value in self.unique:
        self.unique.pop(value)

• First, increment the count of the value in our counter
• If the new count is 1, this value just became unique, so add it to self.unique
• If the value already exists in self.unique (which means its previous count was 1 and now it's 2), remove it since it's no longer unique
• We don't need to handle cases where count goes from 2+ to 3+ since those values aren't in self.unique anyway

Time Complexity:

• __init__: O(n) where n is the length of the initial array
• showFirstUnique(): O(1)
• add(): O(1) average case for hash map operations

Space Complexity: O(n) where n is the total number of unique values seen, as we store each value in the counter and potentially in the OrderedDict.

Example Walkthrough

Let's trace through an example to see how the solution works:

Initial Setup: FirstUnique([7, 7, 7, 7, 7, 3, 3, 17])

1. Constructor execution:

   • Counter creates: {7: 5, 3: 2, 17: 1}
   • Build unique OrderedDict by iterating through [7, 7, 7, 7, 7, 3, 3, 17]:
     • 7 appears 5 times → skip
     • 3 appears 2 times → skip
     • 17 appears 1 time → add to unique
   • Result: unique = OrderedDict({17: 1})

2. Call showFirstUnique():

   • unique is not empty
   • Return first key: 17

3. Call add(17):

   • Update counter: cnt[17] = 2
   • Since count changed from 1 to 2, and 17 is in unique:
     • Remove 17 from unique
   • Result: unique = OrderedDict({}) (empty)

4. Call showFirstUnique():

   • unique is empty
   • Return -1

5. Call add(2):

   • Update counter: cnt[2] = 1
   • Since count is 1 (new unique value):
     • Add 2 to unique
   • Result: unique = OrderedDict({2: 1})

6. Call add(9):

   • Update counter: cnt[9] = 1
   • Since count is 1 (new unique value):
     • Add 9 to unique
   • Result: unique = OrderedDict({2: 1, 9: 1})

7. Call showFirstUnique():

   • unique is not empty
   • Return first key: 2 (maintains insertion order)

8. Call add(2):

   • Update counter: cnt[2] = 2
   • Since count changed from 1 to 2, and 2 is in unique:
     • Remove 2 from unique
   • Result: unique = OrderedDict({9: 1})

9. Call showFirstUnique():

   • unique is not empty
   • Return first key: 9

This walkthrough demonstrates how the OrderedDict maintains insertion order of unique values and efficiently updates when values transition between unique and non-unique states.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(nums): O(n) where n is the length of the input array. This involves iterating through nums twice - once to build the Counter (O(n)) and once to build the OrderedDict comprehension (O(n)).

• showFirstUnique(): O(1) in the average case when there are unique elements. The next() function retrieves the first key from the OrderedDict which is a constant time operation. In the worst case where the OrderedDict is empty, checking emptiness is also O(1).

• add(value): O(1) on average. Incrementing the counter is O(1), checking if count equals 1 is O(1), adding to OrderedDict is O(1), checking membership in OrderedDict is O(1), and popping from OrderedDict is O(1) on average.

Space Complexity:

• O(n) where n is the total number of distinct elements that have been added to the data structure (including initialization).
• The cnt Counter stores all distinct values and their frequencies, taking O(m) space where m is the number of distinct elements.
• The unique OrderedDict stores at most all distinct elements that appear exactly once, which in the worst case is O(m) space.
• Overall space complexity is O(m) where m ≤ n, simplified to O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using a Regular Dictionary Instead of OrderedDict

The Problem: A common mistake is using a regular dict instead of OrderedDict for tracking unique numbers. While Python 3.7+ guarantees insertion order for regular dictionaries, this isn't explicit and can lead to confusion or issues in older Python versions.

# Problematic approach
class FirstUnique:
    def __init__(self, nums: List[int]):
        self.cnt = Counter(nums)
        # Regular dict might not preserve order in older Python versions
        self.unique = {v: 1 for v in nums if self.cnt[v] == 1}

The Solution: Always use OrderedDict to make the ordering guarantee explicit and ensure compatibility:

from collections import OrderedDict

self.unique = OrderedDict({v: 1 for v in nums if self.cnt[v] == 1})

Pitfall 2: Incorrect Order Preservation in Constructor

The Problem: When building the unique dictionary in the constructor, iterating over the Counter's keys instead of the original array loses the original order:

# Wrong - iterates over counter keys which don't preserve original order
self.unique = OrderedDict()
for num, count in self.cnt.items():
    if count == 1:
        self.unique[num] = 1

This would give incorrect results. For example, with nums = [7, 7, 7, 7, 7, 7, 7, 7, 3, 3, 3, 1], the counter's iteration order might place 1 before 3, even though 3 appears first in the original array.

The Solution: Always iterate through the original nums array to preserve insertion order:

self.unique = OrderedDict({v: 1 for v in nums if self.cnt[v] == 1})

Pitfall 3: Inefficient showFirstUnique() Implementation

The Problem: Converting the entire OrderedDict to a list just to get the first element is wasteful:

def showFirstUnique(self) -> int:
    # Inefficient - creates entire list just for first element
    if not self.unique:
        return -1
    return list(self.unique.keys())[0]

The Solution: Use an iterator to get just the first element without creating a full list:

def showFirstUnique(self) -> int:
    if not self.unique:
        return -1
    return next(iter(self.unique.keys()))

Pitfall 4: Forgetting to Handle the Transition from Unique to Non-Unique

The Problem: A critical bug occurs if you forget to remove a number from the unique dictionary when it becomes non-unique:

def add(self, value: int) -> None:
    self.cnt[value] += 1
    if self.cnt[value] == 1:
        self.unique[value] = 1
    # Bug: Forgot to remove value when it's no longer unique!

This would incorrectly keep numbers in the unique dictionary even after they've been added multiple times.

The Solution: Always check if a value needs to be removed from the unique dictionary:

def add(self, value: int) -> None:
    self.cnt[value] += 1
    if self.cnt[value] == 1:
        self.unique[value] = 1
    elif value in self.unique:  # Critical: remove when no longer unique
        self.unique.pop(value)