Smallest number in infinite set

Hash Table Design Heap (Priority Queue) Ordered Set

70.6% acceptance

Jan 13, 2026

1845

232

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...]. Implement SmallestInfiniteSet: SmallestInfiniteSet() - Initializes to contain all positive integers. int popSmallest() - Removes and returns the smallest integer. void addBack(int num) - Adds num back if not already in the set. Example: ["SmallestInfiniteSet","addBack","popSmallest","popSmallest","popSmallest","addBack","popSmallest","popSmallest","popSmallest"] Output: [null,null,1,2,3,null,1,4,5]

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeSet;

pub struct SmallestInfiniteSet {
  min_ptr: i32,
  added_back: BTreeSet<i32>,
}

impl SmallestInfiniteSet {
  pub fn new() -> Self {
    SmallestInfiniteSet { min_ptr: 1, added_back: BTreeSet::new() }
  }

  pub fn pop_smallest(&mut self) -> i32 {
    if let Some(&smallest) = self.added_back.iter().next() {
      if smallest < self.min_ptr {
        self.added_back.remove(&smallest);
        return smallest;
      }
    }
    let val = self.min_ptr;
    self.min_ptr += 1;
    val
  }

  pub fn add_back(&mut self, num: i32) {
    if num < self.min_ptr {
      self.added_back.insert(num);
    }
  }
}