<p>You are given an integer array <code>nums</code> and two integers <code>indexDiff</code> and <code>valueDiff</code>.</p>

<p>Find a pair of indices <code>(i, j)</code> such that:</p>

<ul>
	<li><code>i != j</code>,</li>
	<li><code>abs(i - j) &lt;= indexDiff</code>.</li>
	<li><code>abs(nums[i] - nums[j]) &lt;= valueDiff</code>, and</li>
</ul>

<p>Return <code>true</code><em> if such pair exists or </em><code>false</code><em> otherwise</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
<strong>Output:</strong> true
<strong>Explanation:</strong> We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --&gt; 0 != 3
abs(i - j) &lt;= indexDiff --&gt; abs(0 - 3) &lt;= 3
abs(nums[i] - nums[j]) &lt;= valueDiff --&gt; abs(1 - 1) &lt;= 0
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
<strong>Output:</strong> false
<strong>Explanation:</strong> After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= indexDiff &lt;= nums.length</code></li>
	<li><code>0 &lt;= valueDiff &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int vd) {
        int n = nums.size();
        if (n == 0 || k < 0 || vd < 0)
            return false;

        unordered_map<int, int> mp;

        // bucket_range = vd + 1, ensuring that two numbers in the same bucket
        // or neighboring buckets can have a difference ≤ vd.
        int bucket_range = ((long)vd + 1);

        for (int i = 0; i < n; i++) {

            // Insert the current number into the calculated bucket.
            // So, if the numbers are 4 and 6, and the value diff is 2, then,
            // 4/3 = 1, 6/3 = 2 So, 4 will be put in bucket '1', and 6 will be
            // put in bucket = '2'. since diff between 4 and 6 is 2
            int bucket = nums[i] / bucket_range;
            if (nums[i] < 0)
                --bucket;

            // if already exists, then it will be <= vd ~ 0. return true;
            if (mp.find(bucket) != mp.end())
                return true;
            else {
                mp[bucket] = nums[i];

                // mp.find(bucket - 1) looks for a number in the bucket
                // immediately before the current bucket. If such a number
                // exists, we check if the difference between the current number
                // nums[i] and the number in the previous bucket (mp[bucket -
                // 1])
                //  is at most valueDiff

                if (mp.find(bucket - 1) != mp.end() &&
                    nums[i] - mp[bucket - 1] <= vd)
                    return true;

                // similarly.
                if (mp.find(bucket + 1) != mp.end() &&
                    mp[bucket + 1] - nums[i] <= vd)
                    return true;

                // This ensures that only elements within a window of size k are
                // considered.
                if (mp.size() > k) {

                    // calculates the bucket number for the element that is now
                    // too far back in the array, i.e., nums[i - k].
                    int key_to_remove = nums[i - k] / bucket_range;

                    // he code adjusts the bucket index for negative numbers by
                    // doing --key_to_remove if nums[i - k] is negative (to
                    // ensure correct bucket placement for negative values).
                    if (nums[i - k] < 0)
                        --key_to_remove;

                    mp.erase(key_to_remove);
                }
            }
        }
        return false;
    }
};

// the example where vd = 3 and nums = [1, 7, 12, 15]. The bucket size is vd + 1
// = 4. Now, we'll divide the numbers into buckets and explain why only the
// neighboring buckets (bucket - 1 and bucket + 1) need to be checked.

// Bucket Division:
// nums[0] = 1 → Bucket 0 (range: [0 - 3])
// nums[1] = 7 → Bucket 1 (range: [4 - 7])
// nums[2] = 12 → Bucket 3 (range: [12 - 15])
// nums[3] = 15 → Bucket 3 (range: [12 - 15])

// Since each bucket represents a range of vd + 1 values, any number in bucket -
// 2 or bucket + 2 will have a minimum difference of (vd + 1) * 2, which is
// greater than vd.
133479