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.
1import java.util.PriorityQueue;
2import java.util.Set;
3import java.util.HashSet;
4
5class SmallestInfiniteSet {
6 private PriorityQueue<Integer> pq;
7 private Set<Integer> added;
8 private int current;
9
10 public SmallestInfiniteSet() {
11 pq = new PriorityQueue<>();
12 added = new HashSet<>();
13 current = 1;
14 }
15
16 public int popSmallest() {
17 if (!pq.isEmpty()) {
18 int smallest = pq.poll();
19 added.remove(smallest);
20 return smallest;
21 }
22 return current++;
23 }
24
25 public void addBack(int num) {
26 if (num < current && added.add(num)) {
27 pq.offer(num);
28 }
29 }
30}
31This Java solution maintains a Priority Queue and a HashSet.
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.
Python leverages a direct boolean array approach to manage state: