# Contains Duplicate III
**Difficulty:** HARD
[External](https://leetcode.com/problems/contains-duplicate-iii)
Canonical: https://scaleengineer.com/dsa/problems/contains-duplicate-iii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Bucket Sort](https://scaleengineer.com/algorithms/bucket-sort), [Skip List](https://scaleengineer.com/algorithms/skip-list)
**Data structures:** Array, Ordered Set
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Yandex](https://scaleengineer.com/companies/yandex), [Netflix](https://scaleengineer.com/companies/netflix), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
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`

# Approaches
## Brute Force Approach
Check every possible pair of indices (i,j) in the array and verify if they satisfy all three conditions.
**Time:** O(n²) where n is the length of the array as we need to check every possible pair · **Space:** O(1) as we only use a constant amount of extra space
**Pros:** Simple to implement; No extra space required; Works for all input cases
**Cons:** Very slow for large arrays; Inefficient as it checks all possible pairs; Not suitable for large inputs due to quadratic time complexity
### Explanation
For each index i in the array, we check all possible indices j that come after i. For each pair, we verify:
1. If i and j are different (always true in this case)
2. If the absolute difference between indices (|i-j|) is less than or equal to indexDiff
3. If the absolute difference between values (|nums[i] - nums[j]|) is less than or equal to valueDiff

Here's the implementation:

```java
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (Math.abs(i - j) <= indexDiff && 
                Math.abs((long)nums[i] - nums[j]) <= valueDiff) {
                return true;
            }
        }
    }
    return false;
}
```

Note: We use long for the value difference calculation to handle potential integer overflow cases.
### Algorithm
1. Iterate through each index i from 0 to n-1
2. For each i, iterate through j from i+1 to n-1
3. Check if |i-j| ≤ indexDiff
4. Check if |nums[i] - nums[j]| ≤ valueDiff
5. If both conditions are met, return true
6. If no such pair is found, return false

## Sliding Window with TreeSet Approach
Use a TreeSet to maintain a sorted window of elements and efficiently find elements within the value difference range.
**Time:** O(n log k) where n is the length of array and k is the size of the sliding window (indexDiff) · **Space:** O(k) where k is the size of the sliding window (indexDiff)
**Pros:** More efficient than brute force approach; Handles large inputs better; Maintains only necessary elements in the window
**Cons:** Requires extra space for TreeSet; TreeSet operations are more expensive than simple array operations; More complex implementation
### Explanation
We maintain a sliding window of size indexDiff+1 using a TreeSet. For each number, we try to find an existing number in our set that satisfies the valueDiff condition using TreeSet's ceiling and floor methods.

```java
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
    if (nums == null || nums.length < 2 || indexDiff < 1 || valueDiff < 0) return false;
    
    TreeSet<Long> set = new TreeSet<>();
    
    for (int i = 0; i < nums.length; i++) {
        long curr = nums[i];
        
        // Find the smallest number greater than or equal to curr-valueDiff
        Long floor = set.floor(curr + valueDiff);
        Long ceiling = set.ceiling(curr - valueDiff);
        
        if ((floor != null && floor >= curr) || 
            (ceiling != null && ceiling <= curr)) {
            return true;
        }
        
        set.add(curr);
        
        // Remove the element outside the window
        if (i >= indexDiff) {
            set.remove((long)nums[i - indexDiff]);
        }
    }
    
    return false;
}
```
### Algorithm
1. Create a TreeSet to store numbers in the current window
2. For each number in the array:
   - Check if there exists a number in set within range [curr-valueDiff, curr+valueDiff]
   - Add current number to set
   - Remove number that's outside the window (i-indexDiff)
3. Return true if a valid pair is found, false otherwise

## Bucket Sort Approach
Use bucket sort concept to group numbers into buckets based on their values and check for nearby duplicates.
**Time:** O(n) where n is the length of the array as we only need to traverse the array once · **Space:** O(min(n, k)) where k is indexDiff as we only store elements within the window
**Pros:** Most efficient approach for this problem; O(1) lookup time for potential matches; Handles large inputs efficiently
**Cons:** Requires careful handling of integer overflow; More complex implementation; Uses extra space for storing buckets
### Explanation
We divide the numbers into buckets where each bucket has size valueDiff+1. Numbers that could satisfy the valueDiff condition must fall into the same bucket or adjacent buckets.

```java
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
    if (nums == null || nums.length < 2 || indexDiff < 1 || valueDiff < 0) return false;
    
    Map<Long, Long> buckets = new HashMap<>();
    long w = (long)valueDiff + 1;
    
    for (int i = 0; i < nums.length; i++) {
        long remappedNum = (long)nums[i] - Integer.MIN_VALUE;
        long bucketId = remappedNum / w;
        
        // Check if the current bucket has a number
        if (buckets.containsKey(bucketId)) return true;
        
        // Check adjacent buckets
        if (buckets.containsKey(bucketId - 1) && 
            Math.abs(buckets.get(bucketId - 1) - remappedNum) < w) return true;
        if (buckets.containsKey(bucketId + 1) && 
            Math.abs(buckets.get(bucketId + 1) - remappedNum) < w) return true;
        
        // Add current number to bucket
        buckets.put(bucketId, remappedNum);
        
        // Remove number outside the window
        if (i >= indexDiff) {
            long lastNum = (long)nums[i - indexDiff] - Integer.MIN_VALUE;
            long lastBucketId = lastNum / w;
            buckets.remove(lastBucketId);
        }
    }
    
    return false;
}
```
### Algorithm
1. Create buckets of size valueDiff+1
2. For each number:
   - Calculate its bucket ID
   - Check if same bucket already has a number
   - Check adjacent buckets for numbers within valueDiff range
   - Add current number to its bucket
   - Remove number outside the window
3. Return true if a valid pair is found, false otherwise

# Solutions
### CSharp

```csharp
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;
            }
            index.Add(nums[i], null);
            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;
    }
}
```

### Java

```java
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;
      }
      ts.add((long)nums[i]);
      if (i >= indexDiff) {
        ts.remove((long)nums[i - indexDiff]);
      }
    }
    return false;
  }
}

```

### CPP

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

```

### Python

```python
''' 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('abracadabra') >>> 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 s . add ( v ) 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
```