Problem Statement

Given an integer array nums and two integer k and t, return trueif there are two distinct indicesi and j in the array such that:

• abs(num[i] - nums[j]) ≤ t, and
• abs(i - j) ≤ k

Otherwise, return false.

Examples

Example 1:

Input: nums = [1, 2, 3, 1], k = 3, t = 0
Output: true

Explanation: nums[0] == nums[3], and |0 - 3| = 3 <= k
Also, |1 - 1| = 0 <= t

Example 2:

Input: nums = [1, 0, 1, 1], k = 1, t = 2
Output: true

Explanation: nums[2] == nums[3], |2 - 3| = 1 <= k, and |1 - 1| = 0 <= t

Example 3:

Input: nums = [1, 5, 9, 1, 5, 9], k = 2, t = 3
Output: false

Explanation: No such pair with both distance ≤ 2 and value diff ≤ 3

Constraints:

1 <= nums.length <= 10⁵

-2³¹ <= nums[i] <= 2³¹ - 1 (full 32-bit integer range)

0 <= k <= 10⁵

0 <= t <= 2³¹ - 1

Different Approach

1️⃣ Brute Force Approach

Intuition:

Compare each pair within k distance and check value difference ≤ t.

Code:

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i + 1; j <= i + k && j < nums.size(); ++j) {
            if (abs((long long)nums[i] - nums[j]) <= t)
                return true;
        }
    }
    return false;
}

Complexity Analysis:

• Time Complexity:O(n * k)
• Space Complexity:O(1)

2️⃣ Bucket Sort based Approach

Intuition:

1. Divide the number line into buckets of size valueDiff + 1. If two numbers fall into the same bucket, they differ by ≤ valueDiff.
2. Also check adjacent buckets.

Code:

#include <unordered_map>
#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        // Early exit: it's impossible to satisfy the condition if valueDiff is negative
        if (valueDiff < 0) return false;

        // Hash map to keep track of elements in their respective buckets
        unordered_map<long long, long long> bucket;

        // Width of each bucket: t + 1 to ensure value difference ≤ t for numbers in the same bucket
        long long width = (long long)valueDiff + 1;

        for (int i = 0; i < nums.size(); i++) {
            long long num = (long long)nums[i];

            // Compute the bucket ID (ensure negative numbers are handled correctly)
            long long bucketId = num / width;
            if (num < 0) bucketId--;

            // Step 1: Check if there's already a number in the same bucket
            if (bucket.find(bucketId) != bucket.end()) {
                return true;
            }

            // Step 2: Check the left neighbor bucket
            if (bucket.find(bucketId - 1) != bucket.end()) {
                if (abs(bucket[bucketId - 1] - num) <= valueDiff) {
                    return true;
                }
            }

            // Step 3: Check the right neighbor bucket
            if (bucket.find(bucketId + 1) != bucket.end()) {
                if (abs(bucket[bucketId + 1] - num) <= valueDiff) {
                    return true;
                }
            }

            // Step 4: Place current number in its bucket
            bucket[bucketId] = num;

            // Step 5: Maintain a window of size indexDiff
            // If size exceeds indexDiff, remove the number that's too old
            if (i >= indexDiff) {
                long long oldNum = (long long)nums[i - indexDiff];
                long long oldBucketId = oldNum / width;
                if (oldNum < 0) oldBucketId--;

                bucket.erase(oldBucketId);
            }
        }

        // No such pair found
        return false;
    }
};

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(k)