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 $s_1, s_2, \cdots, s_n$, where $n$ is the number of elements in the ordered set. In this problem, $n \le 1000$.
During initialization, we add all elements in $[1, 1000]$ to the ordered set. The time complexity is $O(n \times \log n)$.
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(\log n)$.
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(\log n)$.
The space complexity is $O(n)$.
1 2 3 4 5 6 7 8 91011121314151617181920
fromsortedcontainersimportSortedSetclassSmallestInfiniteSet:def__init__(self):self.s=SortedSet(range(1,1001))defpopSmallest(self)->int:x=self.s[0]self.s.remove(x)returnxdefaddBack(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)
1 2 3 4 5 6 7 8 9101112131415161718192021222324
classSmallestInfiniteSet{privateTreeSet<Integer>s=newTreeSet<>();publicSmallestInfiniteSet(){for(inti=1;i<=1000;++i){s.add(i);}}publicintpopSmallest(){returns.pollFirst();}publicvoidaddBack(intnum){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); */
classSmallestInfiniteSet{public:SmallestInfiniteSet(){for(inti=1;i<=1000;++i){s.insert(i);}}intpopSmallest(){intx=*s.begin();s.erase(s.begin());returnx;}voidaddBack(intnum){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); */
typeSmallestInfiniteSetstruct{s*treemap.Map}funcConstructor()SmallestInfiniteSet{s:=treemap.NewWithIntComparator()fori:=1;i<=1000;i++{s.Put(i,nil)}returnSmallestInfiniteSet{s}}func(this*SmallestInfiniteSet)PopSmallest()int{x,_:=this.s.Min()this.s.Remove(x.(int))returnx.(int)}func(this*SmallestInfiniteSet)AddBack(numint){this.s.Put(num,nil)}/** * Your SmallestInfiniteSet object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.PopSmallest(); * obj.AddBack(num); */
classSmallestInfiniteSet{privates:TreeSet<number>;constructor(){this.s=newTreeSet();for(leti=1;i<=1000;++i){this.s.add(i);}}popSmallest():number{returnthis.s.shift()!;}addBack(num:number):void{this.s.add(num);}}typeCompare<T>=(lhs:T,rhs:T)=>number;classRBTreeNode<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)returnnull;// sibling null if no parentreturnthis.isOnLeft()?this.parent.right:this.parent.left;}isOnLeft():boolean{returnthis===this.parent!.left;}hasRedChild():boolean{return(Boolean(this.left&&this.left.color===0)||Boolean(this.right&&this.right.color===0));}}classRBTree<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{constright=pt.right!;pt.right=right.left;if(pt.right)pt.right.parent=pt;right.parent=pt.parent;if(!pt.parent)this.root=right;elseif(pt===pt.parent.left)pt.parent.left=right;elsept.parent.right=right;right.left=pt;pt.parent=right;}rotateRight(pt:RBTreeNode<T>):void{constleft=pt.left!;pt.left=left.right;if(pt.left)pt.left.parent=pt;left.parent=pt.parent;if(!pt.parent)this.root=left;elseif(pt===pt.parent.left)pt.parent.left=left;elsept.parent.right=left;left.right=pt;pt.parent=left;}swapColor(p1:RBTreeNode<T>,p2:RBTreeNode<T>):void{consttmp=p1.color;p1.color=p2.color;p2.color=tmp;}swapData(p1:RBTreeNode<T>,p2:RBTreeNode<T>):void{consttmp=p1.data;p1.data=p2.data;p2.data=tmp;}fixAfterInsert(pt:RBTreeNode<T>):void{letparent=null;letgrandParent=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){constuncle=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 */constuncle=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{constnode=this.find(val);if(!node)returnfalse;node.count--;if(!node.count)this.deleteNode(node);returntrue;}deleteAll(val:T):boolean{constnode=this.find(val);if(!node)returnfalse;this.deleteNode(node);returntrue;}deleteNode(v:RBTreeNode<T>):void{constu=BSTreplace(v);// True when u and v are both blackconstuvBlack=(u===null||u.color===1)&&v.color===1;constparent=v.parent!;if(!u){// u is null therefore v is leafif(v===this.root)this.root=null;// v is root, making root nullelse{if(uvBlack){// u and v both black// v is leaf, fix double black at vthis.fixDoubleBlack(v);}else{// u or v is redif(v.sibling()){// sibling is not null, make it red"v.sibling()!.color=0;}}// delete v from the treeif(v.isOnLeft())parent.left=null;elseparent.right=null;}return;}if(!v.left||!v.right){// v has 1 childif(v===this.root){// v is root, assign the value of u to v, and delete uv.data=u.data;v.left=v.right=null;}else{// Detach v from tree and move u upif(v.isOnLeft())parent.left=u;elseparent.right=u;u.parent=parent;if(uvBlack)this.fixDoubleBlack(u);// u and v both black, fix double black at uelseu.color=1;// u or v red, color u black}return;}// v has 2 children, swap data with successor and recursethis.swapData(u,v);this.deleteNode(u);// find node that replaces a deleted node in BSTfunctionBSTreplace(x:RBTreeNode<T>):RBTreeNode<T>|null{// when node have 2 childrenif(x.left&&x.right)returnsuccessor(x.right);// when leafif(!x.left&&!x.right)returnnull;// when single childreturnx.left??x.right;}// find node that do not have a left child// in the subtree of the given nodefunctionsuccessor(x:RBTreeNode<T>):RBTreeNode<T>{lettemp=x;while(temp.left)temp=temp.left;returntemp;}}fixDoubleBlack(x:RBTreeNode<T>):void{if(x===this.root)return;// Reached rootconstsibling=x.sibling();constparent=x.parent!;if(!sibling){// No sibiling, double black pushed upthis.fixDoubleBlack(parent);}else{if(sibling.color===0){// Sibling redparent.color=0;sibling.color=1;if(sibling.isOnLeft())this.rotateRight(parent);// left caseelsethis.rotateLeft(parent);// right casethis.fixDoubleBlack(x);}else{// Sibling blackif(sibling.hasRedChild()){// at least 1 red childrenif(sibling.left&&sibling.left.color===0){if(sibling.isOnLeft()){// left leftsibling.left.color=sibling.color;sibling.color=parent.color;this.rotateRight(parent);}else{// right leftsibling.left.color=parent.color;this.rotateRight(sibling);this.rotateLeft(parent);}}else{if(sibling.isOnLeft()){// left rightsibling.right!.color=parent.color;this.rotateLeft(sibling);this.rotateRight(parent);}else{// right rightsibling.right!.color=sibling.color;sibling.color=parent.color;this.rotateLeft(parent);}}parent.color=1;}else{// 2 black childrensibling.color=0;if(parent.color===1)this.fixDoubleBlack(parent);elseparent.color=1;}}}}insert(data:T):boolean{// search for a position to insertletparent=this.root;while(parent){if(this.lt(data,parent.data)){if(!parent.left)break;elseparent=parent.left;}elseif(this.lt(parent.data,data)){if(!parent.right)break;elseparent=parent.right;}elsebreak;}// insert node into parentconstnode=newRBTreeNode(data);if(!parent)this.root=node;elseif(this.lt(node.data,parent.data))parent.left=node;elseif(this.lt(parent.data,node.data))parent.right=node;else{parent.count++;returnfalse;}node.parent=parent;this.fixAfterInsert(node);returntrue;}find(data:T):RBTreeNode<T>|null{letp=this.root;while(p){if(this.lt(data,p.data)){p=p.left;}elseif(this.lt(p.data,data)){p=p.right;}elsebreak;}returnp??null;}*inOrder(root:RBTreeNode<T>=this.root!):Generator<T,undefined,void>{if(!root)return;for(constvofthis.inOrder(root.left!))yieldv;yieldroot.data;for(constvofthis.inOrder(root.right!))yieldv;}*reverseInOrder(root:RBTreeNode<T>=this.root!):Generator<T,undefined,void>{if(!root)return;for(constvofthis.reverseInOrder(root.right!))yieldv;yieldroot.data;for(constvofthis.reverseInOrder(root.left!))yieldv;}}classTreeSet<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(typeofcollection==='function'){compare=collection;collection=[];}this._size=0;this.compare=compare;this.tree=newRBTree(compare);for(constvalofcollection)this.add(val);}size():number{returnthis._size;}has(val:T):boolean{return!!this.tree.find(val);}add(val:T):boolean{constsuccessful=this.tree.insert(val);this._size+=successful?1:0;returnsuccessful;}delete(val:T):boolean{constdeleted=this.tree.deleteAll(val);this._size-=deleted?1:0;returndeleted;}ceil(val:T):T|undefined{letp=this.tree.root;lethigher=null;while(p){if(this.compare(p.data,val)>=0){higher=p;p=p.left;}else{p=p.right;}}returnhigher?.data;}floor(val:T):T|undefined{letp=this.tree.root;letlower=null;while(p){if(this.compare(val,p.data)>=0){lower=p;p=p.right;}else{p=p.left;}}returnlower?.data;}higher(val:T):T|undefined{letp=this.tree.root;lethigher=null;while(p){if(this.compare(val,p.data)<0){higher=p;p=p.left;}else{p=p.right;}}returnhigher?.data;}lower(val:T):T|undefined{letp=this.tree.root;letlower=null;while(p){if(this.compare(p.data,val)<0){lower=p;p=p.right;}else{p=p.left;}}returnlower?.data;}first():T|undefined{returnthis.tree.inOrder().next().value;}last():T|undefined{returnthis.tree.reverseInOrder().next().value;}shift():T|undefined{constfirst=this.first();if(first===undefined)returnundefined;this.delete(first);returnfirst;}pop():T|undefined{constlast=this.last();if(last===undefined)returnundefined;this.delete(last);returnlast;}*[Symbol.iterator]():Generator<T,void,void>{for(constvalofthis.values())yieldval;}*keys():Generator<T,void,void>{for(constvalofthis.values())yieldval;}*values():Generator<T,undefined,void>{for(constvalofthis.tree.inOrder())yieldval;returnundefined;}/** * Return a generator for reverse order traversing the set */*rvalues():Generator<T,undefined,void>{for(constvalofthis.tree.reverseInOrder())yieldval;returnundefined;}}classTreeMultiSet<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(typeofcollection==='function'){compare=collection;collection=[];}this._size=0;this.compare=compare;this.tree=newRBTree(compare);for(constvalofcollection)this.add(val);}size():number{returnthis._size;}has(val:T):boolean{return!!this.tree.find(val);}add(val:T):boolean{constsuccessful=this.tree.insert(val);this._size++;returnsuccessful;}delete(val:T):boolean{constsuccessful=this.tree.delete(val);if(!successful)returnfalse;this._size--;returntrue;}count(val:T):number{constnode=this.tree.find(val);returnnode?node.count:0;}ceil(val:T):T|undefined{letp=this.tree.root;lethigher=null;while(p){if(this.compare(p.data,val)>=0){higher=p;p=p.left;}else{p=p.right;}}returnhigher?.data;}floor(val:T):T|undefined{letp=this.tree.root;letlower=null;while(p){if(this.compare(val,p.data)>=0){lower=p;p=p.right;}else{p=p.left;}}returnlower?.data;}higher(val:T):T|undefined{letp=this.tree.root;lethigher=null;while(p){if(this.compare(val,p.data)<0){higher=p;p=p.left;}else{p=p.right;}}returnhigher?.data;}lower(val:T):T|undefined{letp=this.tree.root;letlower=null;while(p){if(this.compare(p.data,val)<0){lower=p;p=p.right;}else{p=p.left;}}returnlower?.data;}first():T|undefined{returnthis.tree.inOrder().next().value;}last():T|undefined{returnthis.tree.reverseInOrder().next().value;}shift():T|undefined{constfirst=this.first();if(first===undefined)returnundefined;this.delete(first);returnfirst;}pop():T|undefined{constlast=this.last();if(last===undefined)returnundefined;this.delete(last);returnlast;}*[Symbol.iterator]():Generator<T,void,void>{yield*this.values();}*keys():Generator<T,void,void>{for(constvalofthis.values())yieldval;}*values():Generator<T,undefined,void>{for(constvalofthis.tree.inOrder()){letcount=this.count(val);while(count--)yieldval;}returnundefined;}/** * Return a generator for reverse order traversing the multi-set */*rvalues():Generator<T,undefined,void>{for(constvalofthis.tree.reverseInOrder()){letcount=this.count(val);while(count--)yieldval;}returnundefined;}}/** * Your SmallestInfiniteSet object will be instantiated and called as such: * var obj = new SmallestInfiniteSet() * var param_1 = obj.popSmallest() * obj.addBack(num) */
classSmallestInfiniteSet{privatepq:typeofMinPriorityQueue;privates:Set<number>;constructor(){this.pq=newMinPriorityQueue();this.s=newSet();for(leti=1;i<=1000;i++){this.pq.enqueue(i,i);this.s.add(i);}}popSmallest():number{constx=this.pq.dequeue()?.element;this.s.delete(x);returnx;}addBack(num:number):void{if(!this.s.has(num)){this.pq.enqueue(num,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) */