Smallest Number in Infinite Set

Problem in plain words

Design a class that represents the set of all positive integers 1, 2, 3, …. popSmallest() removes and returns the smallest number currently in the set. addBack(num) puts num back into the set — but only if it is not already there.

Example: pop → 1, pop → 2, addBack(1), pop → 1, pop → 3. Calling addBack(5) at any point does nothing, because 5 was never removed.

Intuition

The set always looks like this: a few scattered small numbers that were added back, followed by an infinite, unbroken run next, next + 1, … that nobody has touched yet. Represent the run with a single integer next. Represent the scattered numbers with a min-heap so the smallest is easy to get, plus a hash set to reject duplicates. Every added-back number is smaller than next, so whenever the heap is non-empty its top is the overall minimum.

Approach

1. Initialise next = 1, an empty min-heap and an empty hash set.
2. popSmallest: if the heap is non-empty, pop its top, remove it from the hash set and return it. Otherwise return next and increment it.
3. addBack(num): if num < next and num is not in the hash set, push it to the heap and add it to the set. If num >= next, it is already in the set, so do nothing.

Dry run

Java solution

class SmallestInfiniteSet {
    private int next;
    private final PriorityQueue<Integer> heap;
    private final Set<Integer> inHeap;

    public SmallestInfiniteSet() {
        next = 1;
        heap = new PriorityQueue<>();
        inHeap = new HashSet<>();
    }

    public int popSmallest() {
        if (!heap.isEmpty()) {
            int smallest = heap.poll();
            inHeap.remove(smallest);
            return smallest;
        }
        return next++;
    }

    public void addBack(int num) {
        if (num < next && inHeap.add(num)) {
            heap.offer(num);
        }
    }
}

Python solution

class SmallestInfiniteSet:

    def __init__(self):
        self.next = 1
        self.heap = []
        self.in_heap = set()

    def popSmallest(self) -> int:
        if self.heap:
            smallest = heapq.heappop(self.heap)
            self.in_heap.remove(smallest)
            return smallest
        self.next += 1
        return self.next - 1

    def addBack(self, num: int) -> None:
        if num < self.next and num not in self.in_heap:
            self.in_heap.add(num)
            heapq.heappush(self.heap, num)

Complexity

Edge cases and common mistakes

• Adding back a number that was never removed — it is already in the set; the num < next check rejects it.
• Duplicate `addBack` calls — without the hash set, the same number would sit in the heap twice and be popped twice.
• Storing all numbers up front — pre-filling 1..1000 works under the constraints but misses the point of an "infinite" set; the counter handles any range.