Smallest Number in Infinite Set

MediumHash TableDesignHeap (Priority Queue)Ordered Set

Solution

export class SmallestInfiniteSet {
  private smallest: number;
  private readonly set: Set<number>;
 
  constructor() {
    this.smallest = 1;
    this.set = new Set();
  }
 
  popSmallest(): number {
    if (this.set.size === 0) {
      this.smallest += 1;
      return this.smallest - 1;
    }
    const smallestFromSet = this.findSmallestFromSet();
    this.set.delete(smallestFromSet);
    return smallestFromSet;
  }
 
  addBack(num: number): void {
    if (num < this.smallest) {
      this.set.add(num);
    }
  }
 
  findSmallestFromSet(): number {
    let smallestFromSet = Number.MAX_SAFE_INTEGER;
    for (const num of this.set) {
      smallestFromSet = Math.min(smallestFromSet, num);
    }
    return smallestFromSet;
  }
}

Complexity

  • npopSmallest의 실행 횟수, maddBack의 실행 횟수
  • Time: O(nm+m)O(n \cdot m + m)
  • Space: O(m)O(m)