Contains Duplicate III

HARD

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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= indexDiff <= nums.length
0 <= valueDiff <= 10⁹

Approaches

Checkout 3 different approaches to solve Contains Duplicate III. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

Check every possible pair of indices (i,j) in the array and verify if they satisfy all three conditions.

Algorithm

Iterate through each index i from 0 to n-1
For each i, iterate through j from i+1 to n-1
Check if |i-j| ≤ indexDiff
Check if |nums[i] - nums[j]| ≤ valueDiff
If both conditions are met, return true
If no such pair is found, return false

For each index i in the array, we check all possible indices j that come after i. For each pair, we verify:

If i and j are different (always true in this case)
If the absolute difference between indices (|i-j|) is less than or equal to indexDiff
If the absolute difference between values (|nums[i] - nums[j]|) is less than or equal to valueDiff

Here's the implementation:

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.

Complexity Analysis

Time Complexity: O(n²) where n is the length of the array as we need to check every possible pairSpace Complexity: O(1) as we only use a constant amount of extra space

Pros and Cons

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

Code Solutions

Checking out 4 solutions in different languages for Contains Duplicate III. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Contains Duplicate III

Algorithms:

SortingBucket Sort

Patterns:

Sliding Window

Data Structures:

ArrayOrdered Set

Companies:

Airbnb |Yandex |Netflix |Palantir Technologies |