Design a number container system that can do the following:
Insert or Replace a number at the given index in the system.
Return the smallest index for the given number in the system.
Implement the NumberContainers class:
NumberContainers() Initializes the number container system.
void change(int index, int number) Fills the container at index with the number. If there is already a number at that index, replace it.
int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number in the system.
Example 1:
Input
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
Output
[null, -1, null, null, null, null, 1, null, 2]
Explanation
NumberContainers nc = new NumberContainers();
nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1.
nc.change(2, 10); // Your container at index 2 will be filled with number 10.
nc.change(1, 10); // Your container at index 1 will be filled with number 10.
nc.change(3, 10); // Your container at index 3 will be filled with number 10.
nc.change(5, 10); // Your container at index 5 will be filled with number 10.
nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1.
nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20.
nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.
Constraints:
1 <= index, number <= 109
At most 105 calls will be made in total to change and find.
Solutions
Solution 1: Hash Table + Ordered Set
We use a hash table $d$ to record the mapping relationship between indices and numbers, and another hash table $g$ to record the set of indices corresponding to each number. Here, we can use an ordered set to store the indices, which allows us to conveniently find the smallest index.
When calling the change method, we first check if the index already exists. If it does, we remove the original number from its corresponding index set and then add the new number to the corresponding index set. The time complexity is $O(\log n)$.
When calling the find method, we simply return the first element of the index set corresponding to the number. The time complexity is $O(1)$.
The space complexity is $O(n)$, where $n$ is the number of numbers.
1 2 3 4 5 6 7 8 910111213141516171819202122232425
fromsortedcontainersimportSortedSetclassNumberContainers:def__init__(self):self.d={}self.g=defaultdict(SortedSet)defchange(self,index:int,number:int)->None:ifindexinself.d:old_number=self.d[index]self.g[old_number].remove(index)self.d[index]=numberself.g[number].add(index)deffind(self,number:int)->int:ids=self.g[number]returnids[0]ifidselse-1# Your NumberContainers object will be instantiated and called as such:# obj = NumberContainers()# obj.change(index,number)# param_2 = obj.find(number)
classNumberContainers{privateMap<Integer,Integer>d=newHashMap<>();privateMap<Integer,TreeSet<Integer>>g=newHashMap<>();publicNumberContainers(){}publicvoidchange(intindex,intnumber){if(d.containsKey(index)){intoldNumber=d.get(index);g.get(oldNumber).remove(index);}d.put(index,number);g.computeIfAbsent(number,k->newTreeSet<>()).add(index);}publicintfind(intnumber){varids=g.get(number);returnids==null||ids.isEmpty()?-1:ids.first();}}/** * Your NumberContainers object will be instantiated and called as such: * NumberContainers obj = new NumberContainers(); * obj.change(index,number); * int param_2 = obj.find(number); */
classNumberContainers{public:NumberContainers(){}voidchange(intindex,intnumber){if(d.contains(index)){intoldNumber=d[index];g[oldNumber].erase(index);if(g[oldNumber].empty()){g.erase(oldNumber);}}d[index]=number;g[number].insert(index);}intfind(intnumber){returng.contains(number)?*g[number].begin():-1;}private:unordered_map<int,int>d;unordered_map<int,set<int>>g;};/** * Your NumberContainers object will be instantiated and called as such: * NumberContainers* obj = new NumberContainers(); * obj->change(index,number); * int param_2 = obj->find(number); */
typeNumberContainersstruct{dmap[int]intgmap[int]*redblacktree.Tree}funcConstructor()NumberContainers{returnNumberContainers{map[int]int{},map[int]*redblacktree.Tree{}}}func(this*NumberContainers)Change(indexint,numberint){ifoldNumber,ok:=this.d[index];ok{this.g[oldNumber].Remove(index)}this.d[index]=numberif_,ok:=this.g[number];!ok{this.g[number]=redblacktree.NewWithIntComparator()}this.g[number].Put(index,nil)}func(this*NumberContainers)Find(numberint)int{ifids,ok:=this.g[number];ok&&ids.Size()>0{returnids.Left().Key.(int)}return-1}/** * Your NumberContainers object will be instantiated and called as such: * obj := Constructor(); * obj.Change(index,number); * param_2 := obj.Find(number); */
classNumberContainers{privated=newMap<number,number>();privateg=newMap<number,TreeSet<number>>();constructor(){}change(index:number,number:number):void{if(this.d.has(index)){constoldNumber=this.d.get(index)!;this.g.get(oldNumber)!.delete(index);if(!this.g.get(oldNumber)!.size()){this.g.delete(oldNumber);}}this.d.set(index,number);if(!this.g.has(number)){this.g.set(number,newTreeSet());}this.g.get(number)!.add(index);}find(number:number):number{returnthis.g.has(number)?this.g.get(number)!.first()!:-1;}}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;}}/** * Your NumberContainers object will be instantiated and called as such: * var obj = new NumberContainers() * obj.change(index,number) * var param_2 = obj.find(number) */