You are given an integer array nums and two integers indexDiff and valueDiff.
Find a pair of indices (i, j) such that:
i != j,
abs(i - j) <= indexDiff.
abs(nums[i] - nums[j]) <= valueDiff, and
Return true if such pair exists or false otherwise.
Example 1:
Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0
Example 2:
Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.
Constraints:
2 <= nums.length <= 105
-109 <= nums[i] <= 109
1 <= indexDiff <= nums.length
0 <= valueDiff <= 109
Solutions
Solution 1: Sliding Window + Ordered Set
We maintain a sliding window of size $k$, and the elements in the window are kept in order.
We traverse the array nums. For each element $nums[i]$, we look for the first element in the ordered set that is greater than or equal to $nums[i] - t$. If the element exists, and this element is less than or equal to $nums[i] + t$, it means we have found a pair of elements that meet the conditions, and we return true. Otherwise, we insert $nums[i]$ into the ordered set, and if the size of the ordered set exceeds $k$, we need to remove the earliest added element from the ordered set.
The time complexity is $O(n \times \log k)$, where $n$ is the length of the array nums. For each element, we need $O(\log k)$ time to find the element in the ordered set, and there are $n$ elements in total, so the total time complexity is $O(n \times \log k)$.
functioncontainsNearbyAlmostDuplicate(nums:number[],indexDiff:number,valueDiff:number,):boolean{constts=newTreeSet<number>();for(leti=0;i<nums.length;++i){constx=ts.ceil(nums[i]-valueDiff);if(x!=null&&x<=nums[i]+valueDiff){returntrue;}ts.add(nums[i]);if(i>=indexDiff){ts.delete(nums[i-indexDiff]);}}returnfalse;}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;}}