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
Top comments (0)