Smallest Number in Infinite Set

Problem Description

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...]. Implement the SmallestInfiniteSet class that initializes the set to contain all positive integers. It should support the following operations:

• popSmallest(): Removes and returns the smallest integer contained in the infinite set.
• addBack(int num): Adds a positive integer num back into the infinite set, if it is not already in the set.

Key Insights

• The set initially contains all positive integers.
• When a number is popped, it is removed from the set.
• A number can be added back to the set if it has been removed previously.
• We need an efficient way to keep track of the smallest number and handle additions back to the set.

Space and Time Complexity

Time Complexity: O(log n) for popSmallest and O(1) for addBack on average. Space Complexity: O(n) in the worst case, where n is the number of numbers added back to the set.

Solution

To implement the SmallestInfiniteSet, we can use a combination of a min-heap (or priority queue) to efficiently retrieve the smallest number and a set to track which numbers are currently available in the infinite set. The min-heap allows us to pop the smallest element in O(log n) time, while the set allows for O(1) time checks to see if a number is available for addition back into the set.

1. Initialize a min-heap to keep track of numbers that have been added back.
2. Maintain a variable to track the next smallest number to be popped from the infinite set.
3. When popSmallest is called, check if there are any numbers in the heap:
   • If the heap is not empty, pop the smallest number from the heap.
   • If the heap is empty, return the current next smallest number and increment it.
4. When addBack is called, add the number to the heap if it is less than the next smallest number and not already in the set.

Code Solutions