Welcome to Subscribe On Youtube

2336. Smallest Number in Infinite Set

Description

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].

Implement the SmallestInfiniteSet class:

  • SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.
  • int popSmallest() Removes and returns the smallest integer contained in the infinite set.
  • void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.

 

Example 1:

Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2);    // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1);    // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
                                   // is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.

 

Constraints:

  • 1 <= num <= 1000
  • At most 1000 calls will be made in total to popSmallest and addBack.

Solutions

Solution 1: Ordered Set + Simulation

We note that the range of elements in the set given by the problem is [1,1000], and the operations we need to support are:

  • popSmallest: Pop the smallest element from the set
  • addBack: Add an element back to the set

Therefore, we can use an ordered set to simulate this. Let’s denote the ordered set as s, and the elements in the set as s1,s2,,sn, where n is the number of elements in the ordered set. In this problem, n1000.

During initialization, we add all elements in [1,1000] to the ordered set. The time complexity is O(n×logn).

In the popSmallest operation, we just need to pop the first element from the ordered set. The time complexity for a single operation is O(logn).

In the addBack operation, we just need to add the element back to the ordered set. The time complexity for a single operation is O(logn).

The space complexity is O(n).

  • class SmallestInfiniteSet {
        private TreeSet<Integer> s = new TreeSet<>();
    
        public SmallestInfiniteSet() {
            for (int i = 1; i <= 1000; ++i) {
                s.add(i);
            }
        }
    
        public int popSmallest() {
            return s.pollFirst();
        }
    
        public void addBack(int num) {
            s.add(num);
        }
    }
    
    /**
     * Your SmallestInfiniteSet object will be instantiated and called as such:
     * SmallestInfiniteSet obj = new SmallestInfiniteSet();
     * int param_1 = obj.popSmallest();
     * obj.addBack(num);
     */
    
  • class SmallestInfiniteSet {
    public:
        SmallestInfiniteSet() {
            for (int i = 1; i <= 1000; ++i) {
                s.insert(i);
            }
        }
    
        int popSmallest() {
            int x = *s.begin();
            s.erase(s.begin());
            return x;
        }
    
        void addBack(int num) {
            s.insert(num);
        }
    
    private:
        set<int> s;
    };
    
    /**
     * Your SmallestInfiniteSet object will be instantiated and called as such:
     * SmallestInfiniteSet* obj = new SmallestInfiniteSet();
     * int param_1 = obj->popSmallest();
     * obj->addBack(num);
     */
    
  • from sortedcontainers import SortedSet
    
    
    class SmallestInfiniteSet:
        def __init__(self):
            self.s = SortedSet(range(1, 1001))
    
        def popSmallest(self) -> int:
            x = self.s[0]
            self.s.remove(x)
            return x
    
        def addBack(self, num: int) -> None:
            self.s.add(num)
    
    
    # Your SmallestInfiniteSet object will be instantiated and called as such:
    # obj = SmallestInfiniteSet()
    # 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);
     */
    
  • class SmallestInfiniteSet {
        private s: TreeSet<number>;
    
        constructor() {
            this.s = new TreeSet();
            for (let i = 1; i <= 1000; ++i) {
                this.s.add(i);
            }
        }
    
        popSmallest(): number {
            return this.s.shift()!;
        }
    
        addBack(num: number): void {
            this.s.add(num);
        }
    }
    
    type Compare<T> = (lhs: T, rhs: T) => number;
    
    class RBTreeNode<T = number> {
        data: T;
        count: number;
        left: RBTreeNode<T> | null;
        right: RBTreeNode<T> | null;
        parent: RBTreeNode<T> | null;
        color: number;
        constructor(data: T) {
            this.data = data;
            this.left = this.right = this.parent = null;
            this.color = 0;
            this.count = 1;
        }
    
        sibling(): RBTreeNode<T> | null {
            if (!this.parent) return null; // sibling null if no parent
            return this.isOnLeft() ? this.parent.right : this.parent.left;
        }
    
        isOnLeft(): boolean {
            return this === this.parent!.left;
        }
    
        hasRedChild(): boolean {
            return (
                Boolean(this.left && this.left.color === 0) ||
                Boolean(this.right && this.right.color === 0)
            );
        }
    }
    
    class RBTree<T> {
        root: RBTreeNode<T> | null;
        lt: (l: T, r: T) => boolean;
        constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
            this.root = null;
            this.lt = (l: T, r: T) => compare(l, r) < 0;
        }
    
        rotateLeft(pt: RBTreeNode<T>): void {
            const right = pt.right!;
            pt.right = right.left;
    
            if (pt.right) pt.right.parent = pt;
            right.parent = pt.parent;
    
            if (!pt.parent) this.root = right;
            else if (pt === pt.parent.left) pt.parent.left = right;
            else pt.parent.right = right;
    
            right.left = pt;
            pt.parent = right;
        }
    
        rotateRight(pt: RBTreeNode<T>): void {
            const left = pt.left!;
            pt.left = left.right;
    
            if (pt.left) pt.left.parent = pt;
            left.parent = pt.parent;
    
            if (!pt.parent) this.root = left;
            else if (pt === pt.parent.left) pt.parent.left = left;
            else pt.parent.right = left;
    
            left.right = pt;
            pt.parent = left;
        }
    
        swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
            const tmp = p1.color;
            p1.color = p2.color;
            p2.color = tmp;
        }
    
        swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
            const tmp = p1.data;
            p1.data = p2.data;
            p2.data = tmp;
        }
    
        fixAfterInsert(pt: RBTreeNode<T>): void {
            let parent = null;
            let grandParent = null;
    
            while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
                parent = pt.parent;
                grandParent = pt.parent.parent;
    
                /*  Case : A
                    Parent of pt is left child of Grand-parent of pt */
                if (parent === grandParent?.left) {
                    const uncle = grandParent.right;
    
                    /* Case : 1
                       The uncle of pt is also red
                       Only Recoloring required */
                    if (uncle && uncle.color === 0) {
                        grandParent.color = 0;
                        parent.color = 1;
                        uncle.color = 1;
                        pt = grandParent;
                    } else {
                        /* Case : 2
                           pt is right child of its parent
                           Left-rotation required */
                        if (pt === parent.right) {
                            this.rotateLeft(parent);
                            pt = parent;
                            parent = pt.parent;
                        }
    
                        /* Case : 3
                           pt is left child of its parent
                           Right-rotation required */
                        this.rotateRight(grandParent);
                        this.swapColor(parent!, grandParent);
                        pt = parent!;
                    }
                } else {
                    /* Case : B
                   Parent of pt is right child of Grand-parent of pt */
                    const uncle = grandParent!.left;
    
                    /*  Case : 1
                        The uncle of pt is also red
                        Only Recoloring required */
                    if (uncle != null && uncle.color === 0) {
                        grandParent!.color = 0;
                        parent.color = 1;
                        uncle.color = 1;
                        pt = grandParent!;
                    } else {
                        /* Case : 2
                           pt is left child of its parent
                           Right-rotation required */
                        if (pt === parent.left) {
                            this.rotateRight(parent);
                            pt = parent;
                            parent = pt.parent;
                        }
    
                        /* Case : 3
                           pt is right child of its parent
                           Left-rotation required */
                        this.rotateLeft(grandParent!);
                        this.swapColor(parent!, grandParent!);
                        pt = parent!;
                    }
                }
            }
            this.root!.color = 1;
        }
    
        delete(val: T): boolean {
            const node = this.find(val);
            if (!node) return false;
            node.count--;
            if (!node.count) this.deleteNode(node);
            return true;
        }
    
        deleteAll(val: T): boolean {
            const node = this.find(val);
            if (!node) return false;
            this.deleteNode(node);
            return true;
        }
    
        deleteNode(v: RBTreeNode<T>): void {
            const u = BSTreplace(v);
    
            // True when u and v are both black
            const uvBlack = (u === null || u.color === 1) && v.color === 1;
            const parent = v.parent!;
    
            if (!u) {
                // u is null therefore v is leaf
                if (v === this.root) this.root = null;
                // v is root, making root null
                else {
                    if (uvBlack) {
                        // u and v both black
                        // v is leaf, fix double black at v
                        this.fixDoubleBlack(v);
                    } else {
                        // u or v is red
                        if (v.sibling()) {
                            // sibling is not null, make it red"
                            v.sibling()!.color = 0;
                        }
                    }
                    // delete v from the tree
                    if (v.isOnLeft()) parent.left = null;
                    else parent.right = null;
                }
                return;
            }
    
            if (!v.left || !v.right) {
                // v has 1 child
                if (v === this.root) {
                    // v is root, assign the value of u to v, and delete u
                    v.data = u.data;
                    v.left = v.right = null;
                } else {
                    // Detach v from tree and move u up
                    if (v.isOnLeft()) parent.left = u;
                    else parent.right = u;
                    u.parent = parent;
                    if (uvBlack) this.fixDoubleBlack(u);
                    // u and v both black, fix double black at u
                    else u.color = 1; // u or v red, color u black
                }
                return;
            }
    
            // v has 2 children, swap data with successor and recurse
            this.swapData(u, v);
            this.deleteNode(u);
    
            // find node that replaces a deleted node in BST
            function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
                // when node have 2 children
                if (x.left && x.right) return successor(x.right);
                // when leaf
                if (!x.left && !x.right) return null;
                // when single child
                return x.left ?? x.right;
            }
            // find node that do not have a left child
            // in the subtree of the given node
            function successor(x: RBTreeNode<T>): RBTreeNode<T> {
                let temp = x;
                while (temp.left) temp = temp.left;
                return temp;
            }
        }
    
        fixDoubleBlack(x: RBTreeNode<T>): void {
            if (x === this.root) return; // Reached root
    
            const sibling = x.sibling();
            const parent = x.parent!;
            if (!sibling) {
                // No sibiling, double black pushed up
                this.fixDoubleBlack(parent);
            } else {
                if (sibling.color === 0) {
                    // Sibling red
                    parent.color = 0;
                    sibling.color = 1;
                    if (sibling.isOnLeft()) this.rotateRight(parent);
                    // left case
                    else this.rotateLeft(parent); // right case
                    this.fixDoubleBlack(x);
                } else {
                    // Sibling black
                    if (sibling.hasRedChild()) {
                        // at least 1 red children
                        if (sibling.left && sibling.left.color === 0) {
                            if (sibling.isOnLeft()) {
                                // left left
                                sibling.left.color = sibling.color;
                                sibling.color = parent.color;
                                this.rotateRight(parent);
                            } else {
                                // right left
                                sibling.left.color = parent.color;
                                this.rotateRight(sibling);
                                this.rotateLeft(parent);
                            }
                        } else {
                            if (sibling.isOnLeft()) {
                                // left right
                                sibling.right!.color = parent.color;
                                this.rotateLeft(sibling);
                                this.rotateRight(parent);
                            } else {
                                // right right
                                sibling.right!.color = sibling.color;
                                sibling.color = parent.color;
                                this.rotateLeft(parent);
                            }
                        }
                        parent.color = 1;
                    } else {
                        // 2 black children
                        sibling.color = 0;
                        if (parent.color === 1) this.fixDoubleBlack(parent);
                        else parent.color = 1;
                    }
                }
            }
        }
    
        insert(data: T): boolean {
            // search for a position to insert
            let parent = this.root;
            while (parent) {
                if (this.lt(data, parent.data)) {
                    if (!parent.left) break;
                    else parent = parent.left;
                } else if (this.lt(parent.data, data)) {
                    if (!parent.right) break;
                    else parent = parent.right;
                } else break;
            }
    
            // insert node into parent
            const node = new RBTreeNode(data);
            if (!parent) this.root = node;
            else if (this.lt(node.data, parent.data)) parent.left = node;
            else if (this.lt(parent.data, node.data)) parent.right = node;
            else {
                parent.count++;
                return false;
            }
            node.parent = parent;
            this.fixAfterInsert(node);
            return true;
        }
    
        find(data: T): RBTreeNode<T> | null {
            let p = this.root;
            while (p) {
                if (this.lt(data, p.data)) {
                    p = p.left;
                } else if (this.lt(p.data, data)) {
                    p = p.right;
                } else break;
            }
            return p ?? null;
        }
    
        *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
            if (!root) return;
            for (const v of this.inOrder(root.left!)) yield v;
            yield root.data;
            for (const v of this.inOrder(root.right!)) yield v;
        }
    
        *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
            if (!root) return;
            for (const v of this.reverseInOrder(root.right!)) yield v;
            yield root.data;
            for (const v of this.reverseInOrder(root.left!)) yield v;
        }
    }
    
    class TreeSet<T = number> {
        _size: number;
        tree: RBTree<T>;
        compare: Compare<T>;
        constructor(
            collection: T[] | Compare<T> = [],
            compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
        ) {
            if (typeof collection === 'function') {
                compare = collection;
                collection = [];
            }
            this._size = 0;
            this.compare = compare;
            this.tree = new RBTree(compare);
            for (const val of collection) this.add(val);
        }
    
        size(): number {
            return this._size;
        }
    
        has(val: T): boolean {
            return !!this.tree.find(val);
        }
    
        add(val: T): boolean {
            const successful = this.tree.insert(val);
            this._size += successful ? 1 : 0;
            return successful;
        }
    
        delete(val: T): boolean {
            const deleted = this.tree.deleteAll(val);
            this._size -= deleted ? 1 : 0;
            return deleted;
        }
    
        ceil(val: T): T | undefined {
            let p = this.tree.root;
            let higher = null;
            while (p) {
                if (this.compare(p.data, val) >= 0) {
                    higher = p;
                    p = p.left;
                } else {
                    p = p.right;
                }
            }
            return higher?.data;
        }
    
        floor(val: T): T | undefined {
            let p = this.tree.root;
            let lower = null;
            while (p) {
                if (this.compare(val, p.data) >= 0) {
                    lower = p;
                    p = p.right;
                } else {
                    p = p.left;
                }
            }
            return lower?.data;
        }
    
        higher(val: T): T | undefined {
            let p = this.tree.root;
            let higher = null;
            while (p) {
                if (this.compare(val, p.data) < 0) {
                    higher = p;
                    p = p.left;
                } else {
                    p = p.right;
                }
            }
            return higher?.data;
        }
    
        lower(val: T): T | undefined {
            let p = this.tree.root;
            let lower = null;
            while (p) {
                if (this.compare(p.data, val) < 0) {
                    lower = p;
                    p = p.right;
                } else {
                    p = p.left;
                }
            }
            return lower?.data;
        }
    
        first(): T | undefined {
            return this.tree.inOrder().next().value;
        }
    
        last(): T | undefined {
            return this.tree.reverseInOrder().next().value;
        }
    
        shift(): T | undefined {
            const first = this.first();
            if (first === undefined) return undefined;
            this.delete(first);
            return first;
        }
    
        pop(): T | undefined {
            const last = this.last();
            if (last === undefined) return undefined;
            this.delete(last);
            return last;
        }
    
        *[Symbol.iterator](): Generator<T, void, void> {
            for (const val of this.values()) yield val;
        }
    
        *keys(): Generator<T, void, void> {
            for (const val of this.values()) yield val;
        }
    
        *values(): Generator<T, undefined, void> {
            for (const val of this.tree.inOrder()) yield val;
            return undefined;
        }
    
        /**
         * Return a generator for reverse order traversing the set
         */
        *rvalues(): Generator<T, undefined, void> {
            for (const val of this.tree.reverseInOrder()) yield val;
            return undefined;
        }
    }
    
    class TreeMultiSet<T = number> {
        _size: number;
        tree: RBTree<T>;
        compare: Compare<T>;
        constructor(
            collection: T[] | Compare<T> = [],
            compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
        ) {
            if (typeof collection === 'function') {
                compare = collection;
                collection = [];
            }
            this._size = 0;
            this.compare = compare;
            this.tree = new RBTree(compare);
            for (const val of collection) this.add(val);
        }
    
        size(): number {
            return this._size;
        }
    
        has(val: T): boolean {
            return !!this.tree.find(val);
        }
    
        add(val: T): boolean {
            const successful = this.tree.insert(val);
            this._size++;
            return successful;
        }
    
        delete(val: T): boolean {
            const successful = this.tree.delete(val);
            if (!successful) return false;
            this._size--;
            return true;
        }
    
        count(val: T): number {
            const node = this.tree.find(val);
            return node ? node.count : 0;
        }
    
        ceil(val: T): T | undefined {
            let p = this.tree.root;
            let higher = null;
            while (p) {
                if (this.compare(p.data, val) >= 0) {
                    higher = p;
                    p = p.left;
                } else {
                    p = p.right;
                }
            }
            return higher?.data;
        }
    
        floor(val: T): T | undefined {
            let p = this.tree.root;
            let lower = null;
            while (p) {
                if (this.compare(val, p.data) >= 0) {
                    lower = p;
                    p = p.right;
                } else {
                    p = p.left;
                }
            }
            return lower?.data;
        }
    
        higher(val: T): T | undefined {
            let p = this.tree.root;
            let higher = null;
            while (p) {
                if (this.compare(val, p.data) < 0) {
                    higher = p;
                    p = p.left;
                } else {
                    p = p.right;
                }
            }
            return higher?.data;
        }
    
        lower(val: T): T | undefined {
            let p = this.tree.root;
            let lower = null;
            while (p) {
                if (this.compare(p.data, val) < 0) {
                    lower = p;
                    p = p.right;
                } else {
                    p = p.left;
                }
            }
            return lower?.data;
        }
    
        first(): T | undefined {
            return this.tree.inOrder().next().value;
        }
    
        last(): T | undefined {
            return this.tree.reverseInOrder().next().value;
        }
    
        shift(): T | undefined {
            const first = this.first();
            if (first === undefined) return undefined;
            this.delete(first);
            return first;
        }
    
        pop(): T | undefined {
            const last = this.last();
            if (last === undefined) return undefined;
            this.delete(last);
            return last;
        }
    
        *[Symbol.iterator](): Generator<T, void, void> {
            yield* this.values();
        }
    
        *keys(): Generator<T, void, void> {
            for (const val of this.values()) yield val;
        }
    
        *values(): Generator<T, undefined, void> {
            for (const val of this.tree.inOrder()) {
                let count = this.count(val);
                while (count--) yield val;
            }
            return undefined;
        }
    
        /**
         * Return a generator for reverse order traversing the multi-set
         */
        *rvalues(): Generator<T, undefined, void> {
            for (const val of this.tree.reverseInOrder()) {
                let count = this.count(val);
                while (count--) yield val;
            }
            return undefined;
        }
    }
    
    /**
     * Your SmallestInfiniteSet object will be instantiated and called as such:
     * var obj = new SmallestInfiniteSet()
     * var 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);
        }
    }/**
     * Your SmallestInfiniteSet object will be instantiated and called as such:
     * let obj = SmallestInfiniteSet::new();
     * let ret_1: i32 = obj.pop_smallest();
     * obj.add_back(num);
     */
    
    

All Problems

All Solutions