Smallest Number in Infinite Set - Video Solutions

Problem Overview: You design a data structure that represents an infinite set of positive integers starting from 1. The structure must support two operations: popSmallest(), which removes and returns the smallest available number, and addBack(num), which inserts a previously removed number back into the set.

Approach 1: Priority Queue + Hash Set (O(log n) per operation)

This approach explicitly tracks numbers that were removed and later reinserted. Maintain a min-heap storing values returned through addBack and a hash set to avoid duplicates. Also keep a pointer current representing the smallest number that has never been popped from the infinite sequence. When popSmallest() runs, compare the heap's smallest element with current. If the heap contains a smaller value, remove it from the heap and set; otherwise return current and increment the pointer. When addBack(num) is called, insert num into the heap only if it is smaller than current and not already tracked in the set. Heap operations cost O(log n) time and the set ensures constant-time membership checks. Space complexity is O(n) for stored reinserted values. This design is a classic combination of heap (priority queue) ordering with fast lookups using a hash table.

Approach 2: Indexed Array with Flags (O(1) amortized)

Because the number of operations is bounded, you can simulate the infinite set using a boolean array that tracks whether a number has been removed or added back. Maintain a pointer pointing to the current smallest candidate. When popSmallest() runs, move the pointer forward until you find an index marked available, mark it removed, and return it. For addBack(num), simply flip the flag back to available if the number was previously removed. Each element is scanned at most once during pointer advancement, giving O(1) amortized time for popSmallest() and O(1) for addBack(). Space complexity is O(n) for the flag array. This approach works well when operation limits are small and avoids the overhead of heap operations or maintaining an ordered set.

Recommended for interviews: The priority queue + set approach is the one most interviewers expect. It models the infinite sequence cleanly using a pointer and handles reinserted values efficiently with heap ordering. Implementing it shows you understand heap behavior, duplicate prevention, and state management in a design-style problem. The indexed array method is simpler but depends on constraints; it demonstrates optimization awareness once the baseline design is clear.