<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:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        if len(nums) <= 1:
            return False
        
        arr = [(val, i) for i, val in enumerate(nums)]
        arr.sort(key=lambda x: (x[0], x[1]))
        l, r = 0, 1 # r is EXCLUSIVE.

        while r < len(arr):
            # Ensures we're within correct value diff
            if arr[r][0] - arr[l][0] <= valueDiff:
                r += 1
                continue
            
            # We've reached an r value that is exclusive.
            while l < r - 1:
                front = arr[l + 1][1]
                back = arr[l][1]
                if front - back <= indexDiff:
                    return True
                l += 1
            
            if arr[r][0] - arr[l][0] <= valueDiff and abs(arr[r][1] - arr[l][1]) <= indexDiff:
                return True

            l += 1
        
        # We've reached an r value that is exclusive.
        while l < r - 1:
            front = arr[l + 1][1]
            back = arr[l][1]
            if front - back <= indexDiff:
                return True
            l += 1
        
        return False


'''
indexDiff = 2
valueDiff = 2
[(0, 2), (3, 0), (4, 3), (6, 1)]
                    ^
                            ^

indexDiff = 3
valueDiff = 0
[(1, 0), (1, 3), (2, 1), (3, 2) ]
 ^                  ^

indexDiff = 2
valueDiff = 3
[(1, 0), (1, 3), (5, 1), (5, 4), (6, 9), (9, 2)]
            ^      ^

indexDiff = 1
valueDiff = 2
[(0, 1), (1, 0), (1, 2), (1, 3)]
    ^       ^




Approach 2
Make every value a tuple that correlates to its index-- (value, index)
Sort this array by value.

Do two pointers-- iterate up to the edge of the valueDiff, then move the left pointer to catch up and see if any satisfy the indexDiff.
When the left pointer reaches the first entry that has the same value, start moving the right pointer again.

'''
38493