Close Readings Nearby

Hard

A sensor has logged its readings in the array readings. You are also given max_gap and tolerance. Decide whether there are two **different** indices i and j such that both hold: - |i - j| ≤ max_gap: the readings were taken close to each other; - |readings[i] - readings[j]| ≤ tolerance: and they almost match. Return True if such a pair exists and False otherwise.

Example 1

readings=[40, 15, 22, 38], max_gap=2, tolerance=5 → False

40 and 38 differ by only 2, but they are 3 positions apart, which is too far. The neighbouring pairs (40, 15), (15, 22), (22, 38) and the pairs one apart, (40, 22) and (15, 38), all differ by more than 5. No pair fits.

Example 2

readings=[40, 15, 22, 38], max_gap=3, tolerance=5 → True

Now a distance of 3 is allowed, so 40 and 38 (indices 0 and 3) fit.

Example 3

readings=[-7, -7], max_gap=1, tolerance=0 → True

Constraints

2 ≤ len(readings) ≤ 10⁵
-10⁹ ≤ readings[i] ≤ 10⁹
1 ≤ max_gap ≤ len(readings)
0 ≤ tolerance ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Bucket Sort Ordered Set Sorting Sliding Window

Similar problems

Narrowest Range Touching Every List Hard A Dark Gap Between Street Lamps Hard Best View for a Turning Camera Hard Nearest Roomy Enough Room Hard Flowers in Bloom on Visit Day Hard

Input

readings=[40, 15, 22, 38], max_gap=2, tolerance=5

Expected

False

Run checks the first 3 tests in your browser. Submit checks all 213 tests on the server, hidden ones included.