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

        n = len(nums)

        nums_dict = {}

        nums_sorted = []

        for index in range(n):

            num = nums[index]

            if num not in nums_dict:

                nums_dict[num] = [index]

            else:

                i = 0

                j = len(nums_dict[num]) - 1

                while i < j:

                    k = (i + j + 1) // 2

                    if nums_dict[num][k] <= index:

                        i = k

                    else:

                        j = k - 1

                if abs(nums_dict[num][i]-index) <= indexDiff:

                    return True

                if nums_dict[num][i] > index:

                    i = -1

                nums_dict[num].insert(i+1,index)

            if len(nums_sorted) == 0:

                nums_sorted.append(num)

            else:

                i = 0

                j = len(nums_sorted) - 1

                while i < j:

                    k = (i + j + 1) // 2

                    if nums_sorted[k] <= num:

                        i = k

                    else:

                        j = k - 1

                if nums_sorted[i] > num:

                    nums_sorted.insert(0,num)

                elif nums_sorted[i] < num:

                    nums_sorted.insert(i+1,num)

        for index in range(len(nums_sorted)-1):

            num = nums_sorted[index]

            for step in range(index+1,len(nums_sorted)):

                if abs(num-nums_sorted[step]) > valueDiff:

                    break

                targets = nums_dict[nums_sorted[step]]

                for target in nums_dict[num]:

                    i = 0

                    j = len(targets) - 1

                    while i < j:

                        k = (i + j + 1) // 2

                        if targets[k] <= target:

                            i = k

                        else:

                            j = k - 1

                    if abs(targets[i] - target) <= indexDiff:

                        return True

                    if i != len(targets) - 1 and abs(targets[i+1] - target) <= indexDiff:

                        return True
                
        return False
40734