Smallest Number in Infinite Set - Practice Coding Problems

Smallest Number in Infinite Set - Problem

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].

Implement the SmallestInfiniteSet class:

SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.
int popSmallest() Removes and returns the smallest integer contained in the infinite set.
void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["SmallestInfiniteSet", "popSmallest", "addBack", "popSmallest"], values = [[], [], [1], []]

› Output: [null, 1, null, 1]

💡 Note: Initialize set with all positive integers. popSmallest() returns 1. addBack(1) puts 1 back. popSmallest() returns 1 again.

Example 2 — Multiple Pops

$ Input: operations = ["SmallestInfiniteSet", "popSmallest", "popSmallest", "addBack", "popSmallest"], values = [[], [], [], [1], []]

› Output: [null, 1, 2, null, 1]

💡 Note: Pop 1, then pop 2. Add 1 back. Next pop returns 1 (smallest available).

Example 3 — No Duplicate Adds

$ Input: operations = ["SmallestInfiniteSet", "addBack", "popSmallest"], values = [[], [1], []]

› Output: [null, null, 1]

💡 Note: Adding 1 when it's already in set has no effect. popSmallest() still returns 1.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Initial State

Set contains all positive integers [1, 2, 3, 4, 5, ...]

Operations

popSmallest removes and returns smallest, addBack restores numbers

Result

Efficient tracking of available numbers

Key Takeaway

🎯 Key Insight: Use a min-heap for returned numbers and a counter for new ones

Asked in

G Google 42 a Amazon 38 Apple 25 M Microsoft 31

The key insight is to split the infinite set into two parts: a min-heap for numbers that were popped and added back, and a counter for the next new number to issue. This avoids storing all infinite numbers while maintaining O(log n) performance. Best approach uses Min-Heap + Counter. Time: O(log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Set Storage	O(n)	O(n)	Store all available numbers in a set and scan to find minimum
Min-Heap with Counter	O(log n)	O(n)	Use a min-heap for returned numbers and counter for next new number

Brute Force with Set Storage — Algorithm Steps

Store all available numbers in a set
For popSmallest: scan from 1 upward to find first available
For addBack: add number to set if not already present

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set contains all numbers 1, 2, 3, 4, 5...

PopSmallest

Scan from 1: check if 1 exists, return and remove it

AddBack

Add number back to the available set

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    bool available[1001];
} SmallestInfiniteSet;

SmallestInfiniteSet* smallestInfiniteSetCreate() {
    SmallestInfiniteSet* obj = (SmallestInfiniteSet*)malloc(sizeof(SmallestInfiniteSet));
    for (int i = 1; i <= 1000; i++) {
        obj->available[i] = true;
    }
    return obj;
}

int smallestInfiniteSetPopSmallest(SmallestInfiniteSet* obj) {
    for (int i = 1; i <= 1000; i++) {
        if (obj->available[i]) {
            obj->available[i] = false;
            return i;
        }
    }
    return -1;
}

void smallestInfiniteSetAddBack(SmallestInfiniteSet* obj, int num) {
    obj->available[num] = true;
}

int main() {
    SmallestInfiniteSet* obj = smallestInfiniteSetCreate();
    printf("[null,%d,null,%d]\n", 
           smallestInfiniteSetPopSmallest(obj),
           (smallestInfiniteSetAddBack(obj, 1), smallestInfiniteSetPopSmallest(obj)));
    free(obj);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

popSmallest scans from 1 up to current minimum, which can be O(n) operations

✓ Linear Growth

Space Complexity

O(n)

Set stores all available numbers, growing with each operation

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Set Storage — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler