2336. Smallest Number in Infinite Set LeetCode Solution

In this guide, you will get 2336. Smallest Number in Infinite Set LeetCode Solution with the best time and space complexity. The solution to Smallest Number in Infinite Set problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Smallest Number in Infinite Set solution in C++
Smallest Number in Infinite Set solution in Java
Smallest Number in Infinite Set solution in Python
Additional Resources

2336. Smallest Number in Infinite Set LeetCode Solution image

Problem Statement of Smallest Number in Infinite Set

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 <= 1000
At most 1000 calls will be made in total to popSmallest and addBack.

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(|\texttt{addBack()}|)

2336. Smallest Number in Infinite Set LeetCode Solution in C++

class SmallestInfiniteSet {
 public:
  int popSmallest() {
    if (added.empty())
      return curr++;
    const int mn = *added.begin();
    added.erase(added.begin());
    return mn;
  }

  void addBack(int num) {
    if (num < curr)
      added.insert(num);
  }

 private:
  int curr = 1;
  set<int> added;
};
/* code provided by PROGIEZ */

2336. Smallest Number in Infinite Set LeetCode Solution in Java

class SmallestInfiniteSet {
  public int popSmallest() {
    if (added.isEmpty())
      return curr++;
    final int mn = added.first();
    added.remove(mn);
    return mn;
  }

  public void addBack(int num) {
    if (num < curr)
      added.add(num);
  }

  private int curr = 1;
  private TreeSet<Integer> added = new TreeSet<>();
}
// code provided by PROGIEZ