Smallest Number in Infinite Set – LeetCode75 Python Solution Explained

The Smallest Number in Infinite Set problem (LeetCode75) is an intriguing data structure challenge that evaluates your ability to manage a dynamic set of numbers efficiently. It tests concepts like tracking availability, state management and iterative searching.

In this blog, we’ll break down the problem, provide examples, explain the Python solution step by step with code snippets, analyze time and space complexity, discuss edge cases and explore real-world applications.

Problem Statement

You have an infinite set of positive integers starting from 1. Implement a class SmallestInfiniteSet with the following functions:

popSmallest() – Removes and returns the smallest number from the set.
addBack(num) – Adds a number back to the set if it has been removed.

Example 1

s = SmallestInfiniteSet()
s.popSmallest()  # Output: 1
s.popSmallest()  # Output: 2
s.addBack(1)
s.popSmallest()  # Output: 1
s.popSmallest()  # Output: 3

Explanation:

Initially, the set is {1, 2, 3, ...}.
popSmallest() removes 1 → {2, 3, ...}.
Next popSmallest() removes 2 → {3, 4, ...}.
addBack(1) adds 1 back → {1, 3, 4, ...}.
Next popSmallest() removes 1 → {3, 4, ...}.

Complete Python Solution

class SmallestInfiniteSet:

    def __init__(self):
        # Boolean array to track removed numbers
        self.seen = [False] * 1005

    def popSmallest(self) -> int:
        # Find the smallest number not yet removed
        for i in range(1, 1005):
            if not self.seen[i]:
                self.seen[i] = True
                return i

    def addBack(self, num: int) -> None:
        # Mark the number as available again
        if num < len(self.seen):
            self.seen[num] = False

Step-by-Step Explanation

Step 1: Initialize the Tracking Array

We use a boolean array seen to keep track of which numbers have been removed. Initially, all numbers are available so we set all values to False.

self.seen = [False] * 1005

Step 2: Pop the Smallest Number

Iterate through the array starting from 1. Return the first number that is not marked removed and mark it as removed.

for i in range(1, 1005):
    if not self.seen[i]:
        self.seen[i] = True
        return i

Step 3: Add a Number Back

To add a number back into the set, mark it as available in the seen array.

if num < len(self.seen):
    self.seen[num] = False

Time and Space Complexity

Time Complexity:
- popSmallest() → O(n) in worst case (iterates through the array until it finds an available number).
- addBack() → O(1) (just marks a value as False).
Space Complexity:
- O(1) for practical purposes (we use a fixed-size array of 1005 elements).

Edge Cases

Repeated popSmallest calls: Works correctly, always returns the next smallest available number.
Adding back numbers already in the set: No effect since the number is already available.
Numbers larger than the array limit (1004): They are ignored in addBack() due to array size.

Real-World Applications

Dynamic Reservation Systems: Manage seat numbers or ticket IDs efficiently.
Task Scheduling: Track task IDs that are currently active or available.
Unique ID Generation: Ensure the smallest unused ID is always allocated.
Inventory Management: Efficiently manage stock items with add/remove operations.

Conclusion

The Smallest Number in Infinite Set problem demonstrates an efficient way to manage a dynamic set of integers with pop and add-back operations. Using a boolean array ensures we can track availability quickly while the logic remains simple and easy to implement.

This problem is highly useful in interview preparation for questions related to state tracking, arrays and dynamic sets.