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 integernum
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 topopSmallest
andaddBack
.
Solutions
Solution 1: Ordered Set + Simulation
We note that the range of elements in the set given by the problem is
popSmallest
: Pop the smallest element from the setaddBack
: Add an element back to the set
Therefore, we can use an ordered set to simulate this. Let’s denote the ordered set as
During initialization, we add all elements in
In the popSmallest
operation, we just need to pop the first element from the ordered set. The time complexity for a single operation is
In the addBack
operation, we just need to add the element back to the ordered set. The time complexity for a single operation is
The space complexity is
-
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); */