Close Readings, Close in Time
Problem
A seismograph logs one integer reading per second in readings. Analysts want to know whether the log contains a near repeat: two different seconds i and j with |i - j| ≤ indexGap and |readings[i] - readings[j]| ≤ valueGap.
Return true if a near repeat exists, otherwise false. The log can be long and both gaps large, so aim for linear time.
Example 1
- Input:
- readings = [10, 40, 23, 12], indexGap = 3, valueGap = 2
- Output:
- true
Seconds 0 and 3 are 3 apart and their readings 10 and 12 differ by 2.
Example 2
- Input:
- readings = [10, 40, 23, 12], indexGap = 2, valueGap = 3
- Output:
- false
Within any 2 seconds the closest readings differ by at least 11.
Constraints
- 1 ≤ readings.length ≤ 10^5
- -10^9 ≤ readings[i] ≤ 10^9
- 1 ≤ indexGap ≤ 10^5
- 0 ≤ valueGap ≤ 2·10^9
Hint
Show the first hint
The index condition is a sliding window of the last indexGap readings. What structure answers 'is any value within valueGap of x?' quickly?
Walkthrough
How to approach it
01Clarify before coding
- Must i and j be different? Yes.
- Are the gap bounds inclusive? Yes, both ≤.
- Can readings be negative? Yes, so bucket ids must use floor division, not truncation.
02Brute force
For each i, compare readings[i] with the next indexGap readings.
Cost: O(n · indexGap): 10^10 comparisons when both are 10^5. A balanced BST over the window gives O(n log k).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.