Sponsored
Sponsored
In this approach, we keep track of removed numbers using a priority queue (min heap) and a set to allow efficient look-up, addition, and removal operations. The priority queue keeps the numbers in sorted order, allowing us to quickly access and remove the smallest number. The set helps us to efficiently check whether a number needs to be added back.
Time Complexity: O(log n) for both pop and add operations, where n is the size of the heap.
Space Complexity: O(n), where n is the size of the heap.
1from heapq import heappop, heappush
2
3class SmallestInfiniteSet:
4 def __init__(self):
5 self.current = 1
6 self.heap = []
7 self.nums_in_heap = set()
8
9 def popSmallest(self) -> int:
10 if self.heap:
11 smallest = heappop(self.heap)
12 self.nums_in_heap.remove(smallest)
13 return smallest
14 smallest = self.current
15 self.current += 1
16 return smallest
17
18 def addBack(self, num: int) -> None:
19 if num < self.current and num not in self.nums_in_heap:
20 heappush(self.heap, num)
21 self.nums_in_heap.add(num)
22Python's solution leverages 'heapq' as a priority queue with an auxiliary set to track numbers.
In this methodology, we use an integer array to monitor the appearance of each number and a boolean flag array to verify if a number is within the set. This leverages more direct array manipulations without complex data structures.
Time Complexity: O(1) for addBack(), O(1) for popSmallest() in average case due to direct access using index.
Space Complexity: O(n), trials with fixed space that holds states up to MAX integers.
This approach leverages direct manipulations with an array marked as a flag to represent the presence of a number.