#2336 - Smallest Number in Infinite Set

MediumHeap / Priority Queue

You have a set containing all positive integers [1, 2, 3, …]. Implement the SmallestInfiniteSet class:

• popSmallest() – removes and returns the smallest integer in the set.
• addBack(num) – adds num back into the set if it is not already present.

Input	Output
Operations	Output
popSmallest(), popSmallest(), popSmallest(), addBack(1), popSmallest(), popSmallest(), popSmallest()	[1, 2, 3, 1, 4, 5, 6]

Solution Space

Try it

/**
 * Maintains an "infinite set" of positive integers with efficient
 * popSmallest and addBack operations.
 *
 * Uses a threshold: all integers >= threshold are implicitly in the set.
 * A sorted set (or min-heap) tracks numbers added back below the threshold.
 */
export class SmallestInfiniteSet {
  private threshold = 1; // all integers >= threshold are in the set
  private addedBack = new Set<number>();

  popSmallest(): number {
    if (this.addedBack.size > 0) {
      const min = Math.min(...this.addedBack);
      this.addedBack.delete(min);
      return min;
    }
    return this.threshold++;
  }

  addBack(num: number): void {
    if (num < this.threshold) {
      this.addedBack.add(num);
    }
    // If num >= threshold, it's already implicitly in the set
  }
}

Approach: threshold + set – track the smallest "natural" number that hasn't been popped (`threshold`). Numbers added back below the threshold go into a Set. `popSmallest` checks the Set first, then falls back to the threshold.

Time: O(n) for `popSmallest` when the added-back set is non-empty (due to `Math.min`); O(1) for `addBack`. Can be improved to O(log n) with a min-heap or sorted set.

Space: O(n) – for the added-back set.

Alternative approaches:

Approach	Idea	Time (pop / add)	Space
Min-heap for addedBack	Replace the plain Set with a min-heap so extracting the minimum is O(log n)	O(log n) / O(log n)	O(n)

Why the Set approach is shown: TypeScript lacks a built-in min-heap, so the Set version keeps the code self-contained. In an interview, mention the heap optimization to demonstrate awareness of the O(n) → O(log n) improvement.

#215 Kth Largest Element in an Array

#2462 Total Cost to Hire K Workers