175. Close in Place and Value
A sensor network records one reading per minute in the array nums. An engineer suspects an echo: two different readings that were taken close together in time and are almost equal in value.
Return true if there exist two different indices i and j such that abs(i - j) <= k and abs(nums[i] - nums[j]) <= t. Otherwise return false. Note that the difference of two readings can be larger than a 32-bit integer can hold, so compute it with care.
Example 1
- Input:
- nums = [10,3,12,40], k = 2, t = 2
- Output:
- true
- Explanation:
Indices 0 and 2 are 2 apart (within k) and the values 10 and 12 differ by 2 (within t), so the answer is true.
Example 2
- Input:
- nums = [5,20,8,30], k = 1, t = 3
- Output:
- false
- Explanation:
Neighbouring readings differ by 15, 12 and 22, all larger than t=3, and k=1 allows nothing else, so the answer is false.
Constraints
1 ≤ nums.length ≤ 105
-231 ≤ nums[i] ≤ 231 - 1
1 ≤ k ≤ 105
0 ≤ t ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(n)
- Space
- O(k)