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.
Example 1:
Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]] Output: [null,2,null,2,null,3,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2); // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 firstUnique.add(3); // the queue is now [2,3,5,5,2,3] firstUnique.showFirstUnique(); // return -1
Example 2:
Input: ["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"] [[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]] Output: [null,-1,null,null,null,null,null,17] Explanation: FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]); firstUnique.showFirstUnique(); // return -1 firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7] firstUnique.add(3); // the queue is now [7,7,7,7,7,7,7,3] firstUnique.add(3); // the queue is now [7,7,7,7,7,7,7,3,3] firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7,3,3,7] firstUnique.add(17); // the queue is now [7,7,7,7,7,7,7,3,3,7,17] firstUnique.showFirstUnique(); // return 17
Example 3:
Input: ["FirstUnique","showFirstUnique","add","showFirstUnique"] [[[809]],[],[809],[]] Output: [null,809,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); // return 809 firstUnique.add(809); // the queue is now [809,809] firstUnique.showFirstUnique(); // return -1
Constraints:
1 <= nums.length <= 10^51 <= nums[i] <= 10^81 <= value <= 10^850000 calls will be made to showFirstUnique and add.class FirstUnique:
def __init__(self, nums: List[int]):
self.queue = collections.deque()
self.uniques = {}
for num in nums:
self.add(num) def showFirstUnique(self) -> int:
while self.queue and not self.uniques[self.queue[0]]:
self.queue.popleft()
if self.queue:
return self.queue[0]
return -1
def add(self, value: int) -> None:
if value not in self.uniques:
self.uniques[value] = True
self.queue.append(value)
else:
self.uniques[value] = FalseIf we are given a problem that requires knowing the count, existence, or visits of values, that is almost always going to require a HashMap or HashSet unless it is a special case where the numbers given are within the range of one to the length of the array or something similar to that.
A HashSet is better for knowing whether a value has been visited, but states and frequencies of numbers are better with a HashMap because the value can be searched in constant time as a hashing key, and its count, index, boolean, or any other desired value can be stored along with it.
We could use a HashMap here to find the first unique number because Python dictionaries are now ordered so we wouldn't need any additional data structure for that. We could just take the numbers from the data stream, see if they are in the dictionary, if they are then we will set its value to false within the dictionary, if they are not then we would initialize it there and mark it as true for being unique.
However, that would require a linear space search if the last value within the dictionary is the only unique one, and we would keep searching through the nonunique values each time the function is called.
To get an optimal time search, we will pair it with a queue that we would also keep each number with and we would pop any nonunique number from it at the beginning of each function call, almost like a sliding window.
This way, the first unique number will always be the leftmost number of the queue.
Let's start by creating our constructor function.
def __init__(self, nums: List[int]):
The function will initialize a queue from the input number array as well as a dictionary of unique values that will contain [value:unique?] pairs.
self.queue = collections.deque()
self.uniques = {}
For each number in the numbers array, we will pass them to our add function and place them into this queue and dictionary.
for num in nums:
self.add(num)
Let's make our add function next.
def add(self, value: int) -> None:
If the current value is not in our dictionary, then it is unique so we will initialize its place there with the initial value of true. We will also append the value to the queue.
if value not in self.uniques:
self.uniques[value] = True
self.queue.append(value)
If the value is in the dictionary already, then we will change its state to false.
else:
self.uniques[value] = False
Lastly, we have our showFirstUnique function.
def showFirstUnique(self) -> int:
Whenever this function is called, we will pop off each nonunique number from the left side of the queue.
while self.queue and not self.uniques[self.queue[0]]:
self.queue.popleft()
Queues are FIFO: first in, first out. This means that we can be sure here that any number on the left side that was not popped from the queue for being nonunique will be the first number that we were given that hasn't been seen more than once.
We will return this leftmost value.
if self.queue:
return self.queue[0]
If our queue has been emptied from us popping each non-unique number, or we never had one to place within it, we will return a negative one.
return -1
By popping each nonunique number from the queue, we are excluding them from any future searches as well so this saves time in the long run.
This pattern can also be useful for more difficult problems later that utilize Monotonic Queues. This allows us to keep one value at the leftmost side of the window that satisfies a certain constraint so that this search doesn't have to be done within each iteration.