Steady Departure Stretch
Earliest longest subarray indices with max-min within a given bound
A city bus control center records the schedule deviation of each departure on one route, in departure order. A negative deviation means the bus departed early, and a positive deviation means it departed late.
You are given an integer array deviations and a nonnegative integer spread. A nonempty contiguous stretch of departures is steady if its largest deviation minus its smallest deviation is at most spread.
Return the inclusive, zero-based indices [start, end] of the longest steady stretch. If multiple stretches have the same maximum length, return the one with the smallest starting index.
If deviations is empty, return [].
Examples
Example 1
Input: deviations = [5,7,6,18,19,17,18], spread = 2 Output: [3,6]
The final four departures have deviations between 17 and 19, so their spread is within the limit. They form a longer steady stretch than the first three departures, and including the departure immediately before them would exceed the limit.
Example 2
Input: deviations = [-4,-4,0,-4,-4], spread = 0 Output: [0,1]
With a spread limit of zero, every departure in a steady stretch must have the same deviation. The two pairs of consecutive departures with deviation -4 tie for the longest stretch, so the earlier pair is selected.
Constraints
- 0 <= deviations.length <= 10000
- -1000000000 <= deviations[i] <= 1000000000
- 0 <= spread <= 2000000000
The intended solution runs in O(n) time and uses O(n) auxiliary space. Index boundaries are inclusive.
Hints
Show hint 1Hint 1
When a window's maximum minus minimum exceeds the limit, extending that window cannot make it valid. Move its left boundary forward instead.
Show hint 2Hint 2
Maintain the window's minimum and maximum in two monotonic deques of indices, removing indices when they leave the window.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you count all steady stretches instead of returning the longest one?
- How would you process departures as a stream while reporting the longest steady stretch seen so far?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem