Longest Tight-Range Stretch

Medium

A sensor logs its readings in the array values. A stretch is a run of consecutive readings. A stretch is tight if the difference between its largest and smallest reading is at most spread. Return the length of the longest tight stretch. A single reading is always a tight stretch.

Example 1

values=[5, 9, 6, 8, 2, 3], spread=3 → 3

The stretch 9, 6, 8 has maximum 9 and minimum 6, a difference of exactly 3. No four consecutive values stay within 3.

Example 2

values=[7, 7, 7, 1], spread=0 → 3

With spread = 0 all values in the stretch must be equal: the three 7s in a row.

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹
0 ≤ spread ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Queue Array Ordered Set Sliding Window Monotonic Queue Heap (Priority Queue)

Similar problems

Steady Stretches of Readings Medium A Dark Gap Between Street Lamps Hard Moving Window Maximum Hard Shortest Stretch Reaching a Total Hard Maximum Sum With Short Hops Hard

Input

values=[5, 9, 6, 8, 2, 3], spread=3

Expected

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