You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].
Implement the SmallestInfiniteSet class:
SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.int popSmallest() Removes and returns the smallest integer contained in the infinite set.void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.
Example 1:
Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]
Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1); // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
// is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.
Constraints:
1 <= num <= 10001000 calls will be made in total to popSmallest and addBack.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.
The implementation uses a min-heap (priority queue) to keep numbers in sorted order. We have a boolean array, present[], to keep track of numbers currently in the heap.
C++
Java
Python
C#
JavaScript
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.
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.
This approach leverages direct manipulations with an array marked as a flag to represent the presence of a number.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Approach using Priority Queue and Set | 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. |
| Approach using Indexed Array and Flags | 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. |
Smallest Number in Infinite Set | 3 Approaches | (MICROSOFT) | Leetcode-1046 | Live Code 🧑🏻💻 • codestorywithMIK • 4,664 views views
Watch 9 more video solutions →Practice Smallest Number in Infinite Set with our built-in code editor and test cases.
Practice on FleetCode