Longest Steady Stretch

MediumSliding Window

Problem

A factory sensor reports temperatures nums. A run of consecutive readings is steady if the difference between its highest and lowest reading is at most limit.

Return the length of the longest steady run.

Example 1

Input:
nums = [5, 9, 6, 13, 11, 10], limit = 3
Output:
3

[13, 11, 10] spans 13 - 10 = 3. Any run of four readings spans more than 3.

Example 2

Input:
nums = [1, 1, 1], limit = 0
Output:
3

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -10^9 ≤ nums[i] ≤ 10^9
  • 0 ≤ limit ≤ 2·10^9

Hint

Show the first hint

If a run is steady, every run inside it is steady too, so a grow-and-shrink window works. The hard part is knowing the window's max and min fast.

Walkthrough

How to approach it

01Clarify before coding

  • Is 'at most limit' inclusive? Yes.
  • Can values be negative? Yes; the difference is what matters.
  • Can limit be 0? Yes; then a steady run is a block of equal values.

02Brute force

For each start, extend right while tracking a running max and min; stop when the spread exceeds limit.

Cost: O(n²) in the worst case (a large limit), about 5·10^9 steps for n = 10^5.

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.

Solve it in the browserStart free

This problem is part of Pro.