2336. Smallest Number in Infinite Set

1. Description

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.

2. Example

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.

3. Constraints

• 1 <= num <= 1000
• At most 1000 calls will be made in total to popSmallest and addBack.

4. Solutions

Hash Table && Heap

n is the operation times
SmallestInfiniteSet
Time complexity: O(1)
Space complexity: O(1)
popSmallest
Time complexity: O(logn)
Space complexity: O(n)
addBack
Time complexity: O(logn)
Space complexity: O(n)

// Use a min-heap to retrieve the smallest element in O(log n).
// An unordered_set is used only for deduplication (average O(1)).
// Overall, popSmallest() is O(log n).
// A single set-based solution also has O(log n) pop, but with larger constants.
class SmallestInfiniteSet {
public:
    SmallestInfiniteSet() {}

    int popSmallest() {
        int smallest = 0;
        if (numbers.empty()) {
            smallest = min_index;
            ++min_index;
        } else {
            smallest = numbers.top();
            numbers.pop();

            number_set.erase(smallest);
        }

        return smallest;
    }

    void addBack(int num) {
        if (num < min_index && number_set.find(num) == number_set.end()) {
            numbers.push(num);

            number_set.insert(num);
        }
    }

private:
    uint64_t min_index = 1;
    unordered_set<int> number_set;
    priority_queue<int, vector<int>, greater<int>> numbers;
};