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

from typing import List

from sortedcontainers import SortedDict


class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        # Idea: Maintains min and max number in windows of size indexDiff to the left of current num
        num_freq_dict = SortedDict()
        for i in range(len(nums)):
            if i >= indexDiff + 1:
                num_to_remove = nums[i - indexDiff - 1]
                num_freq_dict[num_to_remove] -= 1
                if num_freq_dict[num_to_remove] == 0:
                    del (num_freq_dict[num_to_remove])

            curr_num = nums[i]
            if num_freq_dict:
                if self.findMinDiff(curr_num, num_freq_dict.keys()) <= valueDiff:
                    return True

            if curr_num in num_freq_dict:
                num_freq_dict[curr_num] += 1
            else:
                num_freq_dict[curr_num] = 1

        return False

    def findMinDiff(self, num: int, sorted_nums) -> int:
        """
        Binary search to find the min difference between num and any num in the list
        """
        start = 0
        end = len(sorted_nums) - 1
        while end - start > 1:
            mid = (start + end) // 2
            if num == sorted_nums[mid]:
                return 0
            if num < sorted_nums[mid]:
                end = mid
            else:
                start = mid
        return min(abs(num - sorted_nums[start]), abs(sorted_nums[end] - num))

32380