2Brute2Best
🔥0

Smallest Number in Infinite Set

Medium·LeetCode #2336 Pro OnlyBasic Reinforcement
LeetCode
01

Problem Statement

Picture the set of all positive integers: 1, 2, 3, and so on. It never runs out. Build a class SmallestInfiniteSet that starts with every positive integer in it.

  • popSmallest() removes the smallest number still in the set and returns it.
  • addBack(num) puts num back into the set. If num is already in the set, nothing happens.
Input

A series of popSmallest() and addBack(num) calls on a fresh set.

Output

For each popSmallest() call, the number it removed. addBack returns nothing.

Example 1
Input: addBack(2), popSmallest(), popSmallest(), popSmallest(), addBack(1), popSmallest(), popSmallest(), popSmallest()
Output: 1, 2, 3, 1, 4, 5

addBack(2) does nothing, because 2 is still in the set. The first three pops remove 1, 2 and 3. Then addBack(1) puts 1 back, so the next pop returns 1. After that the set continues from 4, so the last two pops return 4 and 5.

Example 2
Input: popSmallest() three times, then addBack(2), addBack(2), popSmallest(), popSmallest()
Output: 1, 2, 3, 2, 4

After three pops the set holds 4, 5, 6, and so on. The second addBack(2) is ignored because 2 is already waiting to come back. So 2 comes out only once, and the next pop skips straight to 4.

Constraints
  • • 1 ≤ num ≤ 1000
  • • At most 1000 calls will be made in total to popSmallest and addBack
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“smallest number still in the set”
→ We need the minimum of a set that keeps changing, so a min-heap or a sorted structure.
“an infinite set of positive integers”
→ We cannot store it all. Almost all of it is untouched, so one counter describes it.
“addBack of a number that may already be there”
→ Duplicates must be ignored, so a hash set guards the heap.
03

Approach Complexity Ladder

Brute Force — one flag per number, scan from 1O(1000)O(1000)

Boolean array of removed numbers; popSmallest scans from 1 for the first one still in the set

Better — sorted set of the numbers still presentO(log 1000)O(1000)

std::set holding every number still in the set; the smallest is begin()

Optimal — counter + min-heap of numbers added backO(log m)O(m)

A counter covers every never-removed number; a min-heap and a hash set hold only the added-back ones

Brute Force Intuition

Keep taken[x] for every number from 1 to 1000. popSmallest scans from 1 and stops at the first number that is not taken, marks it taken, and returns it. addBack(num) clears its flag.

Recognition rule for this sub-pattern:

Items keep arriving; maintain the heap so each query is O(log K) or O(1).
Remember this · Heap — Top K
Trigger
"K largest / smallest / most frequent / closest", kth element, streaming top-K.
Think
Do I really need everything sorted, or only the best K?
Key question
Min-heap or max-heap of size K — which one lets me kick out the worst candidate?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Heap — Top K translate into production architectures and low-level memory mechanics.

LLD Real-World Story

High-Frequency Trading (HFT) Order Book

Price-time priority matching engine powered by heap buckets and tree maps.

Explore Track
C++ Internals

STL Containers & Allocator Internals

std::priority_queue container adapter and underlying heapify memory buffers.

Explore Track
Kth Largest Element in a StreamSeat Reservation Manager