1429. First Unique Number

Problem Description

The problem at hand requires us to keep track of integers as they arrive in a sequence, so we can always query for the first unique integer in this sequence. To clarify, a unique integer is an integer that appears exactly once in the current sequence. We're given a sequence of integers as an array and need to do the following:

• Initialize our data structure with the array of integers.
• Be able to return the value of the first unique integer in the queue at any time.
• Be able to add new integers to the queue.

The problem specifies that if there isn't a unique integer, the showFirstUnique method should return -1. For the purpose of this problem, the 'queue' is a conceptual ordering of the integers; it's not necessarily a queue data structure in the traditional sense where elements are strictly processed in a FIFO (First-In-First-Out) manner, but rather a sequence where we can inspect and count occurrences of integers.

Intuition

Navigating to a solution requires us to address two key operations efficiently: query for the first unique integer, and add new integers to our dataset. A straightforward approach to find unique integers might involve iterating through our data and counting occurrences every time we want to find the first unique integer, but this would be inefficient, particularly as the amount of data grows. Instead, we want to optimize this process.

The given solution takes advantage of two Python data structures—Counter and deque—to handle these operations efficiently:

• Counter: This is a special dictionary provided by Python's collections module that stores elements as keys and their counts as values. This allows us to efficiently keep track of the number of times each integer has been seen.
• deque: A double-ended queue that provides an efficient way to insert and remove elements from both ends, with O(1) time complexity for these operations. It is important here for tracking the order of the integers as they appear and for quick removal of non-unique integers from the front.

For the showFirstUnique method, the implementation uses the deque to keep the integers in order and Counter to know the counts. It pops elements from the deque that are no longer unique (i.e., have a count higher than 1), until it finds an integer that is unique, or if the deque is empty, in which case it returns -1.

The add method needs to take an integer and add it to our data set, which consists of both the Counter and deque. It updates the count of the integer in the Counter, and appends the integer to the deque. This keeps our count accurate, and maintains the correct order for when we need to find the first unique integer.

In summary, the Counter keeps track of occurrences allowing for quick updates and checks, while the deque maintains the order of unique integers efficiently.

Learn more about Queue and Data Stream patterns.

Solution Approach

The problem is addressed by implementing a class FirstUnique with two methods and an initializer:

• __init__(self, nums: List[int]): This is the initializer for our class. It takes a list of integers and initializes two attributes:

  1. self.cnt: A Counter object which records the number of occurrences of each integer in the list.
  2. self.q: A deque which represents our queue and stores the integers in the same order as they appear in the original list.

• showFirstUnique(self) -> int: This method is used to retrieve the value of the first unique integer in the queue. It does so by:

  1. Using a while loop to check the front element of the queue (using self.q[0]).
  2. If the count of the front element in the queue (as stored in self.cnt) is greater than 1, it is not unique; thus, it is removed from the deque using popleft().
  3. This process repeats until a unique integer is found (an integer with a count of 1) or the deque becomes empty.
  4. The method returns -1 if no unique integer is found; otherwise, it returns the first unique integer.

• add(self, value: int) -> None: This method handles adding a new integer to our data structure. When a new value is added:

  1. The Counter is updated to increment the count of the particular value (self.cnt[value] += 1).
  2. The value is appended to the end of the deque (using self.q.append(value)). This ensures the order of integers is maintained.

By maintaining a count of occurrences and the order of inserts, the class efficiently supports querying for unique values and extending the sequence with new values. The Counter allows for constant-time complexity for incrementing and checking counts, and the deque allows for constant-time complexity for adding and removing elements.

Together, these data structures enable the FirstUnique class to perform the necessary operations with an efficient time complexity that avoids the need for repeated scanning of the list of integers.

Example Walkthrough

Let's say we are given the following sequence of integers for our FirstUnique class: [4, 10, 5, 3, 5, 4].

When the FirstUnique object is created with this sequence, the following operations occur during initialization:

• self.cnt is initialized as Counter({4: 2, 10: 1, 5: 2, 3: 1}) showing the count of each number in the sequence.
• self.q is initialized as deque([4, 10, 5, 3, 5, 4]) keeping the original order of numbers.

Now, when showFirstUnique() is called the first time, it performs the following steps:

1. The method starts a loop and examines self.q[0], which is 4.
2. It then checks self.cnt[4], which is 2. Since this is greater than 1, 4 is not unique, so it is removed from self.q using popleft().
3. The next element at the front is 10. The count self.cnt[10] is checked and found to be 1. Therefore, 10 is the first unique number.
4. showFirstUnique() returns 10.

Later, if the add() method is called with the value 3, the following occurs:

• self.cnt[3] becomes 2 as 3 was already present in the sequence.
• 3 is added to self.q, which is now deque([10, 5, 3, 5, 4, 3]).

After this addition, calling showFirstUnique() again starts a check from the front:

1. The front element is 10 with self.cnt[10] still 1, so showFirstUnique() would again return 10.
2. If we had added another 10, then the count would change and the showFirstUnique() process would remove 10 from the queue since its count would be increased, and the next first unique number in the queue would be returned or -1 if there are no unique numbers left.

Through this example, we understand how the FirstUnique class efficiently manages the data with Counter and deque to provide quick access to the first unique integer and accommodates additions to the sequence.

Solution Implementation

Time and Space Complexity

Time Complexity

For the __init__ method:

• Constructing the Counter from the nums list involves counting the frequency of each integer in the list, which has a time complexity of O(n) where n is the number of elements in nums.
• Initializing the deque with nums has a time complexity of O(n) for copying all elements into the deque.

For the showFirstUnique method:

• The while loop in this method can be deceiving, but in the amortized analysis, each element gets dequeued only once due to the nature of the "first unique" constraint. Although in the worst case of a single showFirstUnique call, it could be O(n) where n is the number of elements in the deque, the total operation across all calls is bounded by the number of add operations. Therefore, we consider the amortized time complexity to be O(1).

For the add method:

• Incrementing the counter for a value is O(1).
• Appending the value to the deque is also O(1).

Space Complexity

• The space complexity is O(n) for storing the elements in both the Counter and the deque, where n is the total number of elements that have been added (including duplicates). There is no extra space used that grows with respect to the input size or operations other than what is used to store the numbers and their counts.

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