<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:

    void printSet (const map<int, int> &s){
        map<int, int> ::iterator it;
        for(auto it : s){
            cout << it.first<<" "<<it.second;
        }
        cout <<endl;
    }

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        /*
            Use buckets to find the arrays where the question is to find
            minimum difference between elements or related matter.
            the key to the bucket is nums/(VD+1)
            If two numbers are in the same bucket then their diff<=VD
            if two numbers a,b have the same quotient x when divided by c,
            abs(a-b)<c

            Moreover, if a,b are in different buckets, they MAY have
            abs(a-b)<=VD iff abs(key(a)-key(b))<=1
            So we can check two buckets (x+1), (x-1) for x

            To track the indices, we use the bucket key size
            If there are more than indexDiff (k) keys in the bucket,
            that means we have not found any pair in the last k rounds
            so erase the Least recently added key
        */

        map<int, int> bucket_keys;
        int n = nums.size();
        int vd = valueDiff, id = indexDiff;

        for(int i=0; i<n; i++){
            int q = floor((double)nums[i]/(vd+1));
            if (bucket_keys.find(q)!=bucket_keys.end()) {cout << q<<endl; return true;}
            // we have not found a key
                // add to bucket
                bucket_keys[q] = nums[i];
            if (bucket_keys.find(q-1)!= bucket_keys.end() && abs(bucket_keys[q-1] - bucket_keys[q])<=vd) return true;
            if (bucket_keys.find(q+1)!= bucket_keys.end() && abs(bucket_keys[q+1] - bucket_keys[q])<=vd) return true;
                // if the size is more than id+1
                // erase
                if (bucket_keys.size()==id+1){
                    int last_used_key = floor((double)nums[i-id]/(vd+1));
                    bucket_keys.erase(last_used_key);
                }
                // printSet(bucket_keys);

        }
        return false;

    }
};
130303