# 220. Contains Duplicate III

## Description

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)$.

### Example input

Let’s go through the given code with the example input nums = [1,5,9,1,5,9], indexDiff = 2, and valueDiff = 3 step by step. This code aims to find if there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most valueDiff, and the absolute difference between i and j is at most indexDiff.

### The Code Explained

• SortedSet is a data structure that maintains elements in sorted order. It allows for efficient insertion, deletion, and lookups.
• s.bisect_left(value) finds the index where value should be inserted to keep s sorted.

### Step by Step Iteration

1. Iteration 0: i = 0, v = 1
• s is empty. We add 1 to s. s = [1].
• No element to compare yet, so move to the next iteration.
2. Iteration 1: i = 1, v = 5
• Before the loop, s = [1].
• j = s.bisect_left(5 - 3) = s.bisect_left(2) = 1 (the index where 2 would be inserted).
• j < len(s) is True but s[j] is not <= 8 because s[1] does not exist. We add 5 to s. s = [1, 5].
3. Iteration 2: i = 2, v = 9
• Before the loop, s = [1, 5].
• j = s.bisect_left(9 - 3) = s.bisect_left(6) = 2 (the index where 6 would be inserted).
• j < len(s) is False. We add 9 to s. s = [1, 5, 9].
• i >= indexDiff (2) is True, so we remove nums[0], which is 1. s = [5, 9].
4. Iteration 3: i = 3, v = 1
• Before the loop, s = [5, 9].
• j = s.bisect_left(1 - 3) = s.bisect_left(-2) = 0 (the index where -2 would be inserted, which is the start).
• j < len(s) is True but s[j] is not <= 4 because 5 is not within [-2, 4]. We add 1 to s. s = [1, 5, 9].
• i >= indexDiff is True, so we remove nums[1], which is 5. s = [1, 9].
5. Iteration 4: i = 4, v = 5
• Before the loop, s = [1, 9].
• j = s.bisect_left(5 - 3) = s.bisect_left(2) = 1 (the index where 2 would be inserted).
• j < len(s) is True and s[j] <= 8 is True because 9 is within [2, 8]. This satisfies our condition, so we return True.
• On the 4th iteration, we find that the newly inserted value 5 has a neighbor 9 within the allowed valueDiff of 3, satisfying the condition for nearby almost duplicates.
• Therefore, the function returns True, indicating that the nums array contains at least two elements that fulfill both the indexDiff and valueDiff criteria.
• The use of SortedSet and bisect_left allows for efficient checking of the value difference condition by leveraging the sorted nature of s to quickly find potential candidates for comparison.
• class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
TreeSet<Long> ts = new TreeSet<>();
for (int i = 0; i < nums.length; ++i) {
Long x = ts.ceiling((long) nums[i] - (long) valueDiff);
if (x != null && x <= (long) nums[i] + (long) valueDiff) {
return true;
}
if (i >= indexDiff) {
ts.remove((long) nums[i - indexDiff]);
}
}
return false;
}
}

• class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
set<long> s;
for (int i = 0; i < nums.size(); ++i) {
auto it = s.lower_bound((long) nums[i] - valueDiff);
if (it != s.end() && *it <= (long) nums[i] + valueDiff) return true;
s.insert((long) nums[i]);
if (i >= indexDiff) s.erase((long) nums[i - indexDiff]);
}
return false;
}
};

• '''
Sorted Containers is an Apache2 licensed sorted collections library, written in pure-Python, and fast as C-extensions.

>>> from sortedcontainers import SortedList
>>> sl = SortedList(['e', 'a', 'c', 'd', 'b'])
>>> sl
SortedList(['a', 'b', 'c', 'd', 'e'])
>>> sl *= 10_000_000
>>> sl.count('c')
10000000
>>> sl[-3:]
['e', 'e', 'e']

>>> from sortedcontainers import SortedDict
>>> sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
>>> sd
SortedDict({'a': 1, 'b': 2, 'c': 3})
>>> sd.popitem(index=-1)
('c', 3)

>>> from sortedcontainers import SortedSet
>>> ss
SortedSet(['a', 'b', 'c', 'd', 'r'])
>>> ss.bisect_left('c')
2

ref: https://pypi.org/project/sortedcontainers/
'''

from sortedcontainers import SortedSet

class Solution:
def containsNearbyAlmostDuplicate(
self, nums: List[int], indexDiff: int, valueDiff: int
) -> bool:
s = SortedSet()
for i, v in enumerate(nums):
j = s.bisect_left(v - valueDiff) # then true: s[j] <= v - valueDiff
if j < len(s) and s[j] <= v + valueDiff:
return True
if i >= indexDiff:
s.remove(nums[i - indexDiff])
return False

############

'''
bisect: maintaining a list in sorted order without having to sort the list after each insertion.
https://docs.python.org/3/library/bisect.html

bisect.bisect_left()
Locate the insertion point for x in a to maintain sorted order.

bisect.bisect_right() or bisect.bisect()
Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.

bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)
Insert x in a in sorted order.
Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.insort(a, x, lo=0, hi=len(a), *, key=None)
Similar to insort_left(), but inserting x in a after any existing entries of x.

>>> import bisect
>>> bisect.bisect_left([1,2,3], 2)
1
>>> bisect.bisect_right([1,2,3], 2)
2

>>> a = [1, 1, 1, 2, 3]
>>> bisect.insort_left(a, 1.0)
>>> a
[1.0, 1, 1, 1, 2, 3]

>>> a = [1, 1, 1, 2, 3]
>>> bisect.insort_right(a, 1.0)
>>> a
[1, 1, 1, 1.0, 2, 3]

>>> a = [1, 1, 1, 2, 3]
>>> bisect.insort(a, 1.0)
>>> a
[1, 1, 1, 1.0, 2, 3]
'''

import bisect

class Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
if k == 0:
return False
bst = []
if k < 0 or t < 0:
return False
for i, num in enumerate(nums):
idx = bisect.bisect_left(bst, num)
if idx < len(bst) and abs(bst[idx] - num) <= t:
return True
if idx > 0 and abs(bst[idx - 1] - num) <= t: # idx-1 is because, [3,4,5] and 3.5 insertion-index is 1, but here should check index=0 (i.e. 3), so idx-1
return True
if len(bst) >= k:
del bst[bisect.bisect_left(bst, nums[i - k])]
bisect.insort(bst, num)
return False


• func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
n := len(nums)
left, right := 0, 0
rbt := redblacktree.NewWithIntComparator()
for right < n {
cur := nums[right]
right++
if p, ok := rbt.Floor(cur); ok && cur-p.Key.(int) <= t {
return true
}
if p, ok := rbt.Ceiling(cur); ok && p.Key.(int)-cur <= t {
return true
}
rbt.Put(cur, struct{}{})
if right-left > k {
rbt.Remove(nums[left])
left++
}
}
return false
}

• function containsNearbyAlmostDuplicate(
nums: number[],
indexDiff: number,
valueDiff: number,
): boolean {
const ts = new TreeSet<number>();
for (let i = 0; i < nums.length; ++i) {
const x = ts.ceil(nums[i] - valueDiff);
if (x != null && x <= nums[i] + valueDiff) {
return true;
}
if (i >= indexDiff) {
ts.delete(nums[i - indexDiff]);
}
}
return false;
}

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);
}

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);
}

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;
}
}


• public class Solution {
public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k <= 0 || t < 0) return false;
var index = new SortedList<int, object>();
for (int i = 0; i < nums.Length; ++i) {
if (index.ContainsKey(nums[i])) {
return true;
}
var j = index.IndexOfKey(nums[i]);
if (j > 0 && (long)nums[i] - index.Keys[j - 1] <= t) {
return true;
}
if (j < index.Count - 1 && (long)index.Keys[j + 1] - nums[i] <= t) {
return true;
}
if (index.Count > k) {
index.Remove(nums[i - k]);
}
}
return false;
}
}