Code Implementation

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        if t < 0 or k <= 0:
            return False
        bucket = {}
        width = t + 1
        for i, num in enumerate(nums):
            bucket_id = num // width if num >= 0 else ((num + 1) // width) - 1
            if bucket_id in bucket:
                return True
            if bucket_id - 1 in bucket and abs(num - bucket[bucket_id - 1]) <= t:
                return True
            if bucket_id + 1 in bucket and abs(num - bucket[bucket_id + 1]) <= t:
                return True
            bucket[bucket_id] = num
            if i >= k:
                old_bucket_id = nums[i - k] // width if nums[i - k] >= 0 else ((nums[i - k] + 1) // width) - 1
                del bucket[old_bucket_id]
        return False
      

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (t < 0 || k <= 0) return false;
        unordered_map<long, long> bucket;
        long width = (long)t + 1;
        for (int i = 0; i < nums.size(); ++i) {
            long num = (long)nums[i];
            long bucket_id = num >= 0 ? num / width : ((num + 1) / width) - 1;
            if (bucket.count(bucket_id)) return true;
            if (bucket.count(bucket_id - 1) && abs(num - bucket[bucket_id - 1]) <= t) return true;
            if (bucket.count(bucket_id + 1) && abs(num - bucket[bucket_id + 1]) <= t) return true;
            bucket[bucket_id] = num;
            if (i >= k) {
                long old_num = (long)nums[i - k];
                long old_bucket_id = old_num >= 0 ? old_num / width : ((old_num + 1) / width) - 1;
                bucket.erase(old_bucket_id);
            }
        }
        return false;
    }
};
      

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (t < 0 || k <= 0) return false;
        Map<Long, Long> bucket = new HashMap<>();
        long width = (long)t + 1;
        for (int i = 0; i < nums.length; i++) {
            long num = (long)nums[i];
            long bucketId = num >= 0 ? num / width : ((num + 1) / width) - 1;
            if (bucket.containsKey(bucketId)) return true;
            if (bucket.containsKey(bucketId - 1) && Math.abs(num - bucket.get(bucketId - 1)) <= t) return true;
            if (bucket.containsKey(bucketId + 1) && Math.abs(num - bucket.get(bucketId + 1)) <= t) return true;
            bucket.put(bucketId, num);
            if (i >= k) {
                long oldNum = (long)nums[i - k];
                long oldBucketId = oldNum >= 0 ? oldNum / width : ((oldNum + 1) / width) - 1;
                bucket.remove(oldBucketId);
            }
        }
        return false;
    }
}
      

var containsNearbyAlmostDuplicate = function(nums, k, t) {
    if (t < 0 || k <= 0) return false;
    const bucket = {};
    const width = t + 1;
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const bucketId = num >= 0 ? Math.floor(num / width) : Math.floor((num + 1) / width) - 1;
        if (bucket.hasOwnProperty(bucketId)) return true;
        if (bucket.hasOwnProperty(bucketId - 1) && Math.abs(num - bucket[bucketId - 1]) <= t) return true;
        if (bucket.hasOwnProperty(bucketId + 1) && Math.abs(num - bucket[bucketId + 1]) <= t) return true;
        bucket[bucketId] = num;
        if (i >= k) {
            const oldNum = nums[i - k];
            const oldBucketId = oldNum >= 0 ? Math.floor(oldNum / width) : Math.floor((oldNum + 1) / width) - 1;
            delete bucket[oldBucketId];
        }
    }
    return false;
};
      

Problem Description

You are given an integer array nums and two integers k and t. Your task is to determine if there exist two distinct indices i and j in the array such that:

• The absolute difference between nums[i] and nums[j] is at most t (|nums[i] - nums[j]| ≤ t).
• The absolute difference between i and j is at most k (|i - j| ≤ k).

Constraints:

• Each pair must use different elements (no self-pairing).
• There may be at most one valid solution, and you must not reuse elements.
• The solution must be efficient for large arrays.

Thought Process

At first glance, the problem asks us to find two numbers within a certain distance in the array (by index) that are also close in value (by at most t). The brute-force approach would be to check every pair of indices (i, j) with |i - j| ≤ k and see if their values are within t. However, this would be too slow for large arrays.

To optimize, we need a way to quickly check, for each number, if there is a "nearby" number (by index) whose value is also "close" (by at most t). This is a classic "sliding window" problem, but with the twist that we must also keep track of value proximity, not just index.

The key insight is to maintain a data structure that lets us efficiently:

• Keep track of the last k numbers we've seen (the sliding window).
• For each new number, check if there is any number in the window whose value is within t of it.

Solution Approach

The most efficient and commonly accepted solution uses bucketization to solve both constraints in O(n) time. Here’s how it works, step by step:

1. Define Buckets: Divide the number line into buckets of size t + 1. This way, any two numbers that differ by at most t will either fall into the same bucket or adjacent buckets.
2. Process Each Element: For each number, compute its bucket ID. If the bucket already has a number, we have found two numbers within t difference (since they are in the same bucket).
3. Check Adjacent Buckets: Since two numbers within t could fall into neighboring buckets, we also check the previous and next buckets for a value within t.
4. Maintain Sliding Window: To ensure the indices are within k of each other, we remove the element that falls out of the window (i.e., when i ≥ k, remove nums[i - k] from its bucket).
5. Return Result: If at any point we find a valid pair, return true. If we finish processing the array without finding such a pair, return false.

We use a hash map to represent buckets for O(1) insert, lookup, and delete operations. The bucket ID is computed carefully to handle negative numbers.

Example Walkthrough

Let's walk through an example:
Input: nums = [1, 5, 9, 1, 5, 9], k = 2, t = 3

1. i = 0, num = 1, bucket_id = 0. Bucket is empty. Insert 1 into bucket 0.
2. i = 1, num = 5, bucket_id = 1. No match in bucket 1 or adjacent buckets. Insert 5 into bucket 1.
3. i = 2, num = 9, bucket_id = 2. No match in bucket 2 or adjacent buckets. Insert 9 into bucket 2.
4. i = 3, num = 1, bucket_id = 0. Remove nums[0]=1 from bucket 0 (as it falls out of the window). Bucket 0 is now empty. Insert 1 into bucket 0.
5. i = 4, num = 5, bucket_id = 1. Remove nums[1]=5 from bucket 1. Insert 5 into bucket 1.
6. i = 5, num = 9, bucket_id = 2. Remove nums[2]=9 from bucket 2. Insert 9 into bucket 2.

At no point do we find two numbers within the same or adjacent buckets that satisfy both constraints. So, the function returns false.

If, for example, nums = [1, 2, 3, 1], k = 3, t = 0, then when we reach i = 3, num = 1, and bucket 1 already contains 1 (from i = 0), and i - 0 = 3 ≤ k, so we return true.

Time and Space Complexity

Brute-Force Approach:

• For each index i, check all indices j such that i < j ≤ i + k and test if |nums[i] - nums[j]| ≤ t.
• This results in O(nk) time complexity, which is too slow for large n.
• Space complexity is O(1).

• Each element is inserted and removed from a hash map exactly once.
• Lookup, insert, and remove are all O(1) on average, so the overall time complexity is O(n).
• Space complexity is O(k), since at most k elements are stored in the bucket map at any time (the window size).

Summary

The "Contains Duplicate III" problem combines the sliding window technique with value proximity checks. The elegant solution leverages bucketization to efficiently check, for each number, whether a close-enough value exists nearby in the array. By mapping values to buckets and maintaining a window of size k, we satisfy both the index and value constraints in linear time. This approach avoids brute-force inefficiency and demonstrates how careful data structure selection can lead to optimal solutions.