Skip to content

2336. Smallest Number in Infinite Set 👍

  • Time:
    • Constructor: $O(1)$
    • popSmallest(): $O(\log n)$
    • addBack(num: int): $O(1)$
  • Space: $O(|\texttt{addBack()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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<>();
}