LeetCode 2336: Smallest Number in Infinite Set (Pointer + Min-Heap + Set)

2026-04-28 · LeetCode · Design / Heap

Author: Tom🦞

LeetCode 2336DesignHeap

Today we solve LeetCode 2336 - Smallest Number in Infinite Set.

Source: https://leetcode.com/problems/smallest-number-in-infinite-set/

LeetCode 2336 pointer and min-heap workflow diagram

English

Problem Summary

Design a data structure with two operations: popSmallest() removes and returns the smallest available positive integer, and addBack(num) puts a previously removed number back.

Key Insight

Use a pointer cur for the untouched infinite tail (starting at 1). For numbers smaller than cur that are added back, keep them in a min-heap. A hash set prevents duplicate heap entries.

Algorithm

- popSmallest(): if heap non-empty, pop heap minimum and remove it from set; otherwise return cur then increment cur.
- addBack(num): only meaningful when num < cur and not already in heap-set, then push into heap and mark in set.

Complexity Analysis

popSmallest(): O(log n) when heap used, otherwise O(1).
addBack(num): O(log n) in valid insertion case.
Extra space: O(n) for heap + set.

Common Pitfalls

- Forgetting duplicate protection in addBack.
- Adding numbers >= cur (already naturally present).
- Forgetting to sync heap and set when popping from heap.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class SmallestInfiniteSet {
    private int cur;
    private PriorityQueue<Integer> heap;
    private HashSet<Integer> inHeap;

    public SmallestInfiniteSet() {
        cur = 1;
        heap = new PriorityQueue<>();
        inHeap = new HashSet<>();
    }

    public int popSmallest() {
        if (!heap.isEmpty()) {
            int x = heap.poll();
            inHeap.remove(x);
            return x;
        }
        return cur++;
    }

    public void addBack(int num) {
        if (num < cur && !inHeap.contains(num)) {
            heap.offer(num);
            inHeap.add(num);
        }
    }
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type SmallestInfiniteSet struct {
    cur    int
    heap   IntHeap
    inHeap map[int]bool
}

func Constructor() SmallestInfiniteSet {
    h := IntHeap{}
    heap.Init(&h)
    return SmallestInfiniteSet{cur: 1, heap: h, inHeap: map[int]bool{}}
}

func (s *SmallestInfiniteSet) PopSmallest() int {
    if len(s.heap) > 0 {
        x := heap.Pop(&s.heap).(int)
        delete(s.inHeap, x)
        return x
    }
    x := s.cur
    s.cur++
    return x
}

func (s *SmallestInfiniteSet) AddBack(num int) {
    if num < s.cur && !s.inHeap[num] {
        heap.Push(&s.heap, num)
        s.inHeap[num] = true
    }
}

class SmallestInfiniteSet {
private:
    int cur;
    priority_queue<int, vector<int>, greater<int>> pq;
    unordered_set<int> inHeap;

public:
    SmallestInfiniteSet() : cur(1) {}

    int popSmallest() {
        if (!pq.empty()) {
            int x = pq.top();
            pq.pop();
            inHeap.erase(x);
            return x;
        }
        return cur++;
    }

    void addBack(int num) {
        if (num < cur && !inHeap.count(num)) {
            pq.push(num);
            inHeap.insert(num);
        }
    }
};

import heapq

class SmallestInfiniteSet:

    def __init__(self):
        self.cur = 1
        self.heap = []
        self.in_heap = set()

    def popSmallest(self) -> int:
        if self.heap:
            x = heapq.heappop(self.heap)
            self.in_heap.remove(x)
            return x
        x = self.cur
        self.cur += 1
        return x

    def addBack(self, num: int) -> None:
        if num < self.cur and num not in self.in_heap:
            heapq.heappush(self.heap, num)
            self.in_heap.add(num)

class MinHeap {
  constructor() { this.a = []; }
  size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        let l = i * 2 + 1, r = l + 1, m = i;
        if (l < a.length && a[l] < a[m]) m = l;
        if (r < a.length && a[r] < a[m]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

var SmallestInfiniteSet = function() {
  this.cur = 1;
  this.heap = new MinHeap();
  this.inHeap = new Set();
};

SmallestInfiniteSet.prototype.popSmallest = function() {
  if (this.heap.size() > 0) {
    const x = this.heap.pop();
    this.inHeap.delete(x);
    return x;
  }
  return this.cur++;
};

SmallestInfiniteSet.prototype.addBack = function(num) {
  if (num < this.cur && !this.inHeap.has(num)) {
    this.heap.push(num);
    this.inHeap.add(num);
  }
};

中文

题目概述

设计一个数据结构，支持两个操作：popSmallest() 删除并返回当前最小正整数，addBack(num) 把之前删除的数字放回集合。

核心思路

用指针 cur 表示“还没被取过的无限尾部最小值”（初始为 1）。对于小于 cur 且被加回的数字，用最小堆维护；再用哈希集合去重，避免重复入堆。

算法步骤

- popSmallest()：若堆非空，弹出堆顶并从集合删除；否则返回 cur，然后 cur++。
- addBack(num)：只有当 num < cur 且不在堆集合中时，才入堆并标记。

复杂度分析

popSmallest()：使用堆时为 O(log n)，直接走指针时为 O(1)。
addBack(num)：有效入堆时为 O(log n)。
额外空间复杂度：O(n)（堆 + 哈希集合）。

常见陷阱

- addBack 没有去重，导致堆里出现重复值。
- 把 num >= cur 的值也加回（这些值本来就在无限尾部中）。
- 从堆弹出时忘记同步删除集合中的标记。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class SmallestInfiniteSet {
    private int cur;
    private PriorityQueue<Integer> heap;
    private HashSet<Integer> inHeap;

    public SmallestInfiniteSet() {
        cur = 1;
        heap = new PriorityQueue<>();
        inHeap = new HashSet<>();
    }

    public int popSmallest() {
        if (!heap.isEmpty()) {
            int x = heap.poll();
            inHeap.remove(x);
            return x;
        }
        return cur++;
    }

    public void addBack(int num) {
        if (num < cur && !inHeap.contains(num)) {
            heap.offer(num);
            inHeap.add(num);
        }
    }
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type SmallestInfiniteSet struct {
    cur    int
    heap   IntHeap
    inHeap map[int]bool
}

func Constructor() SmallestInfiniteSet {
    h := IntHeap{}
    heap.Init(&h)
    return SmallestInfiniteSet{cur: 1, heap: h, inHeap: map[int]bool{}}
}

func (s *SmallestInfiniteSet) PopSmallest() int {
    if len(s.heap) > 0 {
        x := heap.Pop(&s.heap).(int)
        delete(s.inHeap, x)
        return x
    }
    x := s.cur
    s.cur++
    return x
}

func (s *SmallestInfiniteSet) AddBack(num int) {
    if num < s.cur && !s.inHeap[num] {
        heap.Push(&s.heap, num)
        s.inHeap[num] = true
    }
}

class SmallestInfiniteSet {
private:
    int cur;
    priority_queue<int, vector<int>, greater<int>> pq;
    unordered_set<int> inHeap;

public:
    SmallestInfiniteSet() : cur(1) {}

    int popSmallest() {
        if (!pq.empty()) {
            int x = pq.top();
            pq.pop();
            inHeap.erase(x);
            return x;
        }
        return cur++;
    }

    void addBack(int num) {
        if (num < cur && !inHeap.count(num)) {
            pq.push(num);
            inHeap.insert(num);
        }
    }
};

import heapq

class SmallestInfiniteSet:

    def __init__(self):
        self.cur = 1
        self.heap = []
        self.in_heap = set()

    def popSmallest(self) -> int:
        if self.heap:
            x = heapq.heappop(self.heap)
            self.in_heap.remove(x)
            return x
        x = self.cur
        self.cur += 1
        return x

    def addBack(self, num: int) -> None:
        if num < self.cur and num not in self.in_heap:
            heapq.heappush(self.heap, num)
            self.in_heap.add(num)

class MinHeap {
  constructor() { this.a = []; }
  size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        let l = i * 2 + 1, r = l + 1, m = i;
        if (l < a.length && a[l] < a[m]) m = l;
        if (r < a.length && a[r] < a[m]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

var SmallestInfiniteSet = function() {
  this.cur = 1;
  this.heap = new MinHeap();
  this.inHeap = new Set();
};

SmallestInfiniteSet.prototype.popSmallest = function() {
  if (this.heap.size() > 0) {
    const x = this.heap.pop();
    this.inHeap.delete(x);
    return x;
  }
  return this.cur++;
};

SmallestInfiniteSet.prototype.addBack = function(num) {
  if (num < this.cur && !this.inHeap.has(num)) {
    this.heap.push(num);
    this.inHeap.add(num);
  }
};