Smallest Number in Infinite Set solution and explanation

from heapq import heappop, heappush

class SmallestInfiniteSet:
    def __init__(self):
        self.current = 1
        self.heap = []
        self.nums_in_heap = set()

    def popSmallest(self) -> int:
        if self.heap:
            smallest = heappop(self.heap)
            self.nums_in_heap.remove(smallest)
            return smallest
        smallest = self.current
        self.current += 1
        return smallest

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

import java.util.PriorityQueue;
import java.util.Set;
import java.util.HashSet;

class SmallestInfiniteSet {
    private PriorityQueue<Integer> pq;
    private Set<Integer> added;
    private int current;

    public SmallestInfiniteSet() {
        pq = new PriorityQueue<>();
        added = new HashSet<>();
        current = 1;
    }

    public int popSmallest() {
        if (!pq.isEmpty()) {
            int smallest = pq.poll();
            added.remove(smallest);
            return smallest;
        }
        return current++;
    }

    public void addBack(int num) {
        if (num < current && added.add(num)) {
            pq.offer(num);
        }
    }
}

#include <set>
using namespace std;

class SmallestInfiniteSet {
    set<int> nums;
    int currentSmallest = 1;
public:
    SmallestInfiniteSet() {
        for (int i = 1; i <= 1000; ++i) {
            nums.insert(i);
        }
    }
    int popSmallest() {
        int smallest = *nums.begin();
        nums.erase(nums.begin());
        nums.insert(currentSmallest + 1000);
        currentSmallest++;
        return smallest;
    }
    void addBack(int num) {
        if (num < currentSmallest)
            nums.insert(num);
    }
};

class SmallestInfiniteSet {
    constructor() {
        this.current = 1;
        this.set = new Set();
    }

    popSmallest() {
        if (this.set.size > 0) {
            const min = Math.min(...this.set);
            this.set.delete(min);
            return min;
        }
        return this.current++;
    }

    addBack(num) {
        if (num < this.current && !this.set.has(num))
            this.set.add(num);
    }
}

/* Please note that C doesn't have a built-in priority queue. Below is a custom implementation using a min-heap, which might not be directly executable without additional heap functions. */
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000

typedef struct {
    int* heap;
    int size;
    bool present[MAX_SIZE + 1];
} SmallestInfiniteSet;

SmallestInfiniteSet* smallestInfiniteSetCreate() {
    SmallestInfiniteSet* obj = malloc(sizeof(SmallestInfiniteSet));
    obj->heap = malloc(sizeof(int) * (MAX_SIZE + 1));
    obj->size = 0;
    for (int i = 0; i <= MAX_SIZE; ++i) {
        obj->present[i] = true;
    }
    return obj;
}

void heapify(int* heap, int size, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < size && heap[left] < heap[smallest])
        smallest = left;

    if (right < size && heap[right] < heap[smallest])
        smallest = right;

    if (smallest != index) {
        int temp = heap[index];
        heap[index] = heap[smallest];
        heap[smallest] = temp;

        heapify(heap, size, smallest);
    }
}

void insertHeap(SmallestInfiniteSet* obj, int num) {
    int i;
    i = obj->size++;
    obj->heap[i] = num;

    while (i && obj->heap[i] < obj->heap[(i - 1) / 2]) {
        int temp = obj->heap[i];
        obj->heap[i] = obj->heap[(i - 1) / 2];
        obj->heap[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

int removeMin(SmallestInfiniteSet* obj) {
    if (obj->size <= 0)
        return INT_MAX;
    if (obj->size == 1) {
        obj->size--;
        return obj->heap[0];
    }
    int root = obj->heap[0];
    obj->heap[0] = obj->heap[--obj->size];
    heapify(obj->heap, obj->size, 0);
    return root;
}

int smallestInfiniteSetPopSmallest(SmallestInfiniteSet* obj) {
    int smallest = removeMin(obj);
    obj->present[smallest] = false;
    return smallest;
}

void smallestInfiniteSetAddBack(SmallestInfiniteSet* obj, int num) {
    if (!obj->present[num]) {
        insertHeap(obj, num);
        obj->present[num] = true;
    }
}

void smallestInfiniteSetFree(SmallestInfiniteSet* obj) {
    free(obj->heap);
    free(obj);
}

using System;
using System.Collections.Generic;

public class SmallestInfiniteSet {
    private SortedSet<int> set;
    private int current;

    public SmallestInfiniteSet() {
        set = new SortedSet<int>();
        current = 1;
    }

    public int PopSmallest() {
        if (set.Count > 0) {
            int smallest = set.Min;
            set.Remove(smallest);
            return smallest;
        }
        return current++;
    }

    public void AddBack(int num) {
        if (num < current && !set.Contains(num))
            set.Add(num);
    }
}

class SmallestInfiniteSet:
    def __init__(self):
        self.available = [True] * 1001
        self.smallest = 1

    def popSmallest(self) -> int:
        # Find the next available smallest number
        while not self.available[self.smallest]:
            self.smallest += 1
        # Mark the number as unavailable
        self.available[self.smallest] = False
        # Return the smallest number
        return self.smallest

    def addBack(self, num: int) -> None:
        # Mark number as available
        if not self.available[num]:
            self.smallest = min(self.smallest, num)
        self.available[num] = True

public class SmallestInfiniteSet {
    private boolean[] available;
    private int currentSmallest;

    public SmallestInfiniteSet() {
        available = new boolean[1001];
        for (int i = 1; i <= 1000; i++) {
            available[i] = true;
        }
        currentSmallest = 1;
    }

    public int popSmallest() {
        while (!available[currentSmallest]) {
            currentSmallest++;
        }
        available[currentSmallest] = false;
        return currentSmallest++;
    }

    public void addBack(int num) {
        if (!available[num] && num < currentSmallest) {
            currentSmallest = num;
        }
        available[num] = true;
    }
}

#include <vector>
#include <set>
using namespace std;

class SmallestInfiniteSet {
    vector<bool> available;
    int currentSmallest;
public:
    SmallestInfiniteSet() : available(1001, true), currentSmallest(1) {}

    int popSmallest() {
        while (!available[currentSmallest]) currentSmallest++;
        available[currentSmallest] = false;
        return currentSmallest;
    }

    void addBack(int num) {
        if (!available[num] && num < currentSmallest) currentSmallest = num;
        available[num] = true;
    }
};

class SmallestInfiniteSet {
    constructor() {
        this.available = new Array(1001).fill(true);
        this.current = 1;
    }

    popSmallest() {
        while (!this.available[this.current]) {
            this.current++;
        }
        this.available[this.current] = false;
        return this.current;
    }

    addBack(num) {
        if (num < this.current) {
            this.current = num;
        }
        this.available[num] = true;
    }
}

/* Directly manipulate with indexed arrays and flags */
#include <stdbool.h>
#include <stdlib.h>

#define MAX 1000

typedef struct {
    bool available[MAX + 1];
    int smallest;
} SmallestInfiniteSet;

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

int smallestInfiniteSetPopSmallest(SmallestInfiniteSet* obj) {
    while (!obj->available[obj->smallest]) {
        obj->smallest++;
    }
    int val = obj->smallest;
    obj->available[val] = false;
    return val;
}

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

void smallestInfiniteSetFree(SmallestInfiniteSet* obj) {
    free(obj);
}

public class SmallestInfiniteSet {
    private bool[] available;
    private int currentSmallest;

    public SmallestInfiniteSet() {
        available = new bool[1001];
        for (int i = 1; i <= 1000; i++) {
            available[i] = true;
        }
        currentSmallest = 1;
    }

    public int PopSmallest() {
        while (!available[currentSmallest]) {
            currentSmallest++;
        }
        available[currentSmallest] = false;
        return currentSmallest++;
    }

    public void AddBack(int num) {
        if (!available[num] && num < currentSmallest) {
            currentSmallest = num;
        }
        available[num] = true;
    }
}

class SmallestInfiniteSet {
    private pq = new MinPriorityQueue<number>();
    private s = new Set<number>();

    constructor() {
        for (let i = 1; i <= 1000; i++) {
            this.pq.enqueue(i);
            this.s.add(i);
        }
    }

    popSmallest(): number {
        const x = this.pq.dequeue();
        this.s.delete(x);
        return x;
    }

    addBack(num: number): void {
        if (!this.s.has(num)) {
            this.pq.enqueue(num);
            this.s.add(num);
        }
    }
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * var obj = new SmallestInfiniteSet()
 * var param_1 = obj.popSmallest()
 * obj.addBack(num)
 */

type SmallestInfiniteSet struct {
	s *treemap.Map
}

func Constructor() SmallestInfiniteSet {
	s := treemap.NewWithIntComparator()
	for i := 1; i <= 1000; i++ {
		s.Put(i, nil)
	}
	return SmallestInfiniteSet{s}
}

func (this *SmallestInfiniteSet) PopSmallest() int {
	x, _ := this.s.Min()
	this.s.Remove(x.(int))
	return x.(int)
}

func (this *SmallestInfiniteSet) AddBack(num int) {
	this.s.Put(num, nil)
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.PopSmallest();
 * obj.AddBack(num);
 */

use std::collections::BTreeSet;

struct SmallestInfiniteSet {
    s: BTreeSet<i32>,
}

impl SmallestInfiniteSet {
    fn new() -> Self {
        let mut set = BTreeSet::new();
        for i in 1..=1000 {
            set.insert(i);
        }
        SmallestInfiniteSet { s: set }
    }

    fn pop_smallest(&mut self) -> i32 {
        let x = *self.s.iter().next().unwrap();
        self.s.remove(&x);
        x
    }

    fn add_back(&mut self, num: i32) {
        self.s.insert(num);
    }
}