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.
1#include <set>
2using namespace std;
3
4class SmallestInfiniteSet {
5 set<int> nums;
6 int currentSmallest = 1;
7public:
8 SmallestInfiniteSet() {
9 for (int i = 1; i <= 1000; ++i) {
10 nums.insert(i);
11 }
12 }
13 int popSmallest() {
14 int smallest = *nums.begin();
15 nums.erase(nums.begin());
16 nums.insert(currentSmallest + 1000);
17 currentSmallest++;
18 return smallest;
19 }
20 void addBack(int num) {
21 if (num < currentSmallest)
22 nums.insert(num);
23 }
24};
25In this C++ solution, we use a set to automatically sort and manage the 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.
Python leverages a direct boolean array approach to manage state: