< Previous
Next >
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
[Array]
[Sliding Window]
[Sorting]
[Bucket Sort]
[Ordered Set]
Similar Questions
- Contains Duplicate (Easy)
- Contains Duplicate II (Easy)
Hints
Hint 1
Time complexity O(n logk) - This will give an indication that sorting is involved for k elements.
Hint 2
Use already existing state to evaluate next state - Like, a set of k sorted numbers are only needed to be tracked. When we are processing the next number in array, then we can utilize the existing sorted state and it is not necessary to sort next overlapping set of k numbers again.