Smallest Number in Infinite Set

Problem

Design a data structure that conceptually contains all positive integers 1, 2, 3, ... (an infinite set). Implement a class SmallestInfiniteSet supporting:

• SmallestInfiniteSet() — initialize the set so it contains every positive integer.
• popSmallest() -> int — remove and return the smallest integer currently in the set.
• addBack(num) -> None — add the positive integer num back into the set, but only if it is not already present (adding a number that is still in the set does nothing).

The challenge is that the set is infinite, so you cannot materialize all its elements. You must track only what has changed relative to the pristine 1, 2, 3, ... sequence.

Examples

• Sequence of calls: addBack(2) → set already contains 2, no-op. popSmallest() → returns 1 (set now conceptually {2, 3, 4, ...}). popSmallest() → returns 2. popSmallest() → returns 3. addBack(1) → 1 was popped, so it re-enters; set is {1, 4, 5, ...}. popSmallest() → returns 1 (the re-added value is now the smallest). popSmallest() → returns 4. popSmallest() → returns 5.

• Fresh instance: popSmallest() returns 1, then 2, then 3 — the naturals in order until something is added back.

Constraints

• 1 <= num <= 1000.
• At most 1000 total calls to popSmallest and addBack combined.
• popSmallest is always called when the set is non-empty (it never runs dry, since the set is infinite).

Think about it first

TL;DR

Track the infinite tail with one integer pointer, and keep only the added-back-below-the-pointer numbers in a min-heap guarded by a set — popSmallest is O(log n), addBack is O(log n), O(n) space.

Approach 1 — Naive design: a boolean array of “present” flags

Since num <= 1000, the naive design ignores the “infinite” framing and just tracks presence for 1..1000 with a boolean array, scanning for the smallest present value on each pop. (This is a pure design problem — there is no algorithmic “brute force” beyond a simpler design, so the ladder starts here.)

class SmallestInfiniteSet:
    def __init__(self) -> None:
        self.present = [True] * 1001  # indices 1..1000

    def popSmallest(self) -> int:
        for num in range(1, 1001):
            if self.present[num]:
                self.present[num] = False
                return num
        return -1  # unreachable given the problem's bounds

    def addBack(self, num: int) -> None:
        self.present[num] = True

Complexity: popSmallest is O(M) where M = 1000 (linear scan), addBack is O(1), space O(M). This passes the given limits but leans entirely on the tiny num <= 1000 bound; it does not honor the “infinite set” spirit and degrades if that cap grows. The linear scan per pop is the waste to remove.

Approach 2 — Integer pointer for the tail + min-heap for the exceptions

The insight: the set is always the pristine sequence current, current + 1, current + 2, ... plus a handful of numbers below current that were popped and later added back. So represent it with two pieces:

• an integer current = the smallest number never yet popped from the tail (starts at 1);
• a min-heap holding the added-back numbers that are strictly less than current, with a companion set so we never push a duplicate.

A min-heap (binary heap) is a tree that always yields its minimum in O(1) and supports O(log n) push/pop. popSmallest returns the heap’s top when the heap is non-empty (those are all < current, hence smaller than the tail); otherwise it returns current and advances the pointer. addBack(num) only matters when num < current and num is not already tracked.

import heapq
from typing import List, Set

class SmallestInfiniteSet:
    def __init__(self) -> None:
        self.current = 1
        self.added_heap: List[int] = []
        self.added_set: Set[int] = set()

    def popSmallest(self) -> int:
        if self.added_heap:
            smallest = heapq.heappop(self.added_heap)
            self.added_set.remove(smallest)
            return smallest
        smallest = self.current
        self.current += 1
        return smallest

    def addBack(self, num: int) -> None:
        # Only numbers already popped (num < current) can re-enter,
        # and only if not already waiting in the heap.
        if num < self.current and num not in self.added_set:
            heapq.heappush(self.added_heap, num)
            self.added_set.add(num)

Walkthrough on the example call sequence:

• addBack(2): current = 1, so 2 < 1 is false → no-op. (2 is still in the tail.)
• popSmallest(): heap empty → return current = 1, advance current to 2.
• popSmallest(): heap empty → return 2, current becomes 3.
• popSmallest(): heap empty → return 3, current becomes 4.
• addBack(1): 1 < 4 and not tracked → push 1; heap [1], set {1}.
• popSmallest(): heap non-empty → pop 1, remove from set → return 1.
• popSmallest(): heap empty → return current = 4, current becomes 5.
• popSmallest(): heap empty → return 5.

Returned sequence 1, 2, 3, 1, 4, 5 matches the expected output.

Complexity: popSmallest O(log n), addBack O(log n), where n is the number of exceptions currently below current. Space O(n). Nothing depends on the 1000 cap, so this scales to a genuinely infinite set.

Common pitfalls

• Pushing a value that is still in the tail. If num >= current, it was never removed, so addBack must ignore it — otherwise popSmallest could return it twice.
• Allowing duplicates in the heap. Two addBack(3) calls without an intervening pop must not queue 3 twice; the companion set enforces “add only if not present.”
• Forgetting to sync the set on pop. When you pop a value out of the heap, remove it from the set too, or a later legitimate addBack of that value will be wrongly rejected.
• Comparing the heap top against current incorrectly. Everything in the heap is by construction < current, so a non-empty heap always wins — no extra comparison is needed, but the invariant must be maintained by addBack.

Pattern takeaway

When a structure is “mostly a regular sequence with a few exceptions,” don’t store the regular part — capture it with a cursor and keep only the exceptions in a heap. A pointer for the predictable tail plus a min-heap (guarded by a set for uniqueness) is a reusable recipe for “give me the current smallest, and let things be added back” designs.