Contains Duplicate III

Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Constraints:

• 1 <= nums.length <= 2 * 104
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 104
• 0 <= t <= 231 - 1

SOLUTION:

import bisect

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        indices = {}
        for i, el in enumerate(nums):
            if el in indices:
                indices[el].append(i)
            else:
                indices[el] = [i]
        vals = sorted(indices.keys())
        n = len(vals)
        for i in range(n):
            j = i
            while j < n and vals[j] - vals[i] <= t:
                for a in indices[vals[i]]:
                    b = bisect.bisect_right(indices[vals[j]], a)
                    b = min(b, len(indices[vals[j]]) - 1)
                    bi = indices[vals[j]][b - 1]
                    bj = indices[vals[j]][b]
                    if 0 < abs(a - bj) <= k or 0 < abs(a - bi) <= k:
                        return True
                j += 1
        return False