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.
1class SmallestInfiniteSet {
2 constructor() {
3 this.current = 1;
4 this.set = new Set();
5 }
6
7 popSmallest() {
8 if (this.set.size > 0) {
9 const min = Math.min(...this.set);
10 this.set.delete(min);
11 return min;
12 }
13 return this.current++;
14 }
15
16 addBack(num) {
17 if (num < this.current && !this.set.has(num))
18 this.set.add(num);
19 }
20}
21JavaScript's Set efficiently handles uniqueness and storage of our modified 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.
Java implements this solution through a boolean array that distinctly marks when integers are part of the set: