LeetCode 75
Smallest Number in Infinite Set
- Problem
- LC 2336
- Topic
- Heap / PQ
- File
- official75_LC2336SmallestNumberInInfiniteSet.java
- Path
- pkg5leetcode/official75/official75_LC2336SmallestNumberInInfiniteSet.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC2336SmallestNumberInInfiniteSet.java
- Approach
- TreeSet for removed numbers; counter for next fresh.
- Complexity
- Time O(log n) per op, Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Smallest Number in Infinite Set | LC 23365 * APPROACH: TreeSet for removed numbers; counter for next fresh.6 * COMPLEXITY: Time O(log n) per op, Space O(n)7 */8import java.util.*;9 10public class official75_LC2336SmallestNumberInInfiniteSet {11 static class SmallestInfiniteSet {12 TreeSet<Integer> removed = new TreeSet<>();13 int next = 1;14 15 int popSmallest() {16 if (!removed.isEmpty()) {17 int v = removed.pollFirst();18 return v;19 }20 return next++;21 }22 23 void addBack(int num) {24 if (num < next && removed.add(num)) { /* restored */ }25 }26 }27 28 public static void main(String[] args) {29 SmallestInfiniteSet set = new SmallestInfiniteSet();30 set.addBack(2);31 check(set.popSmallest() == 1, "case1");32 check(set.popSmallest() == 2, "case2");33 check(set.popSmallest() == 3, "case3");34 set.addBack(1);35 check(set.popSmallest() == 1, "case4");36 check(set.popSmallest() == 4, "case5");37 check(set.popSmallest() == 5, "case6");38 System.out.println("all tests passed");39 }40 41 static void check(boolean cond, String name) {42 if (!cond) throw new AssertionError("FAILED: " + name);43 System.out.println(" PASS " + name);44 }45}