Abstract / Summary

Find the smallest positive integer not in a set built by repeatedly adding multiples of a given number to a starting value.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 71% (300k+ submissions).

Typical patterns to solve this problem:

• Design
• Hash Table
• Heap (Priority Queue)
• Ordered Set

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The class implements a mutable infinite set of positive integers that supports extracting the smallest element and re-inserting previously removed values. It relies on a fixed-size bitset to represent membership of numbers up to a predefined bound and maintains a cursor (lowpos) that always points to the current smallest present element. The design avoids dynamic containers such as std::set and instead uses constant-time bit operations combined with a linear scan that is bounded by the size of the bitset.

Core Data Members

bitset<1002> inf;
int lowpos;

inf stores a Boolean flag for each integer index. Index 0 is reserved as a sentinel and is always cleared. Indices 1…1001 correspond to the values that can be present in the set. lowpos holds the smallest index whose flag is true; it is one-based to match the problem domain.

Constructor

SmallestInfiniteSet() {
    lowpos = 1;     // one-based
    inf.set();
    inf[0] = false; // stop-marker
}

The constructor initializes the set to contain every positive integer within the supported range. inf.set() marks all bits as true, then the sentinel at position 0 is cleared. lowpos starts at 1 because the smallest possible element is 1.

popSmallest

int popSmallest() {
    int result = lowpos;
    inf[lowpos] = false;
    while (!inf[lowpos])
        lowpos++;
    return result;
}

The method returns the current smallest element (lowpos). It clears the corresponding bit to indicate removal. The subsequent while loop advances lowpos until it reaches the next true bit, guaranteeing that lowpos always points to the smallest present element after the operation. Because the bitset size is fixed, the loop never runs past the sentinel at index 0, which remains false.

addBack

void addBack(int num) {
    inf[num] = true;
    if (num < lowpos)
        lowpos = num;
    else
        while (!inf[lowpos])
            lowpos++;
}

When a number is re-inserted, its bit is set to true. If the inserted value is smaller than the current cursor, lowpos is moved back directly to that value, ensuring immediate availability as the smallest element. Otherwise, the method verifies that the cursor still points to a true bit; if the previously smallest element was removed and the set became empty up to lowpos, the loop advances lowpos to the next true position.

Edge Cases Handled

The sentinel bit at index 0 guarantees that any forward scan will eventually encounter a false value, preventing an out-of-bounds read. When the set becomes empty (all bits cleared except the sentinel), lowpos will advance past the highest valid index and stop at the sentinel, which correctly reflects the absence of any element. Adding back a number that is already present simply sets the bit again; the cursor logic ensures that lowpos does not move unnecessarily if the added value is not smaller than the current smallest.

When addBack receives a value equal to lowpos, the first branch (num < lowpos) is bypassed, and the subsequent loop confirms that the bit at lowpos is true, leaving the cursor unchanged. This preserves the invariant that lowpos always points to a true bit after any operation.

Performance Optimizations

The use of a bitset provides O(1) access for setting and clearing membership flags, eliminating the overhead of node allocation and pointer chasing that a balanced tree would incur. The cursor (lowpos) eliminates the need to search from the beginning of the bitset on each popSmallest; it only moves forward when necessary, making successive removals amortized constant time.

In addBack, the conditional check if (num < lowpos) allows an immediate jump back to a smaller value without scanning, which is optimal when re-inserting a number that becomes the new minimum. The fallback loop runs only when the inserted number does not affect the current minimum, and it quickly verifies that the cursor still points to a valid element, avoiding unnecessary work.

Because the bitset size is bounded (1002 bits), all loops have a deterministic upper bound, and the overall memory footprint is fixed and small, leading to predictable cache behavior. The sentinel at index 0 also serves as a cheap termination condition for scans, avoiding extra boundary checks.

Imagine a long row of numbered light switches stretching out toward the horizon. Each switch represents a number starting from one. At the very beginning, every single switch is turned on, meaning all the numbers are available to be picked.

The code uses a special tool that keeps track of which lights are still on. When someone asks for the smallest number, the program looks at the first switch that is turned on. It remembers that number and then flips that switch off so it cannot be used again. After that, it quickly walks down the line of switches to find the new first light that is still shining brightly so it is ready for the next request.

Sometimes, a number needs to be added back into the collection. When that happens, the program turns that specific switch back on. If the new number is smaller than the ones currently being checked, the program shifts its attention to that new, smaller number. If the number is larger, the program stays where it is and makes sure the current position is ready to be used whenever a request comes in. It is like having a magical box of numbers that you can take from and put back whenever you like, while the program keeps a careful lookout for the smallest one still hiding inside.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python		Java	C++			TS
	WalkCCC			Java	C++
	leetcode.ca	Python		Java	C++	Go	Rust	TS
	Progiez	Python		Java	C++
github	charles-wangkai			Java
	everthis		JS
	fsq				C++
	JoshCrozier		JS
	lkwq007	Python
	trung-hn	Python
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
trung-hn	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality