Count Steady Stretches

MediumSliding Window

Problem

Using the same idea of steadiness, a run of consecutive readings in nums is steady if its highest and lowest values differ by at most limit.

Return how many non-empty contiguous subarrays of nums are steady.

Example 1

Input:
nums = [3, 1, 4, 2], limit = 2
Output:
6

The four single readings, plus [3, 1] (spread 2) and [4, 2] (spread 2). [1, 4] spreads 3, so nothing longer works.

Example 2

Input:
nums = [7, 7, 7], limit = 0
Output:
6

All 6 subarrays have spread 0.

Constraints

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

Hint

Show the first hint

Count by right end: how many steady subarrays end at index r?

Walkthrough

How to approach it

01Clarify before coding

  • Inclusive limit? Yes.
  • How large can the answer be? Up to n(n + 1)/2 ≈ 5·10^9: use 64-bit counters in typed languages.
  • Do equal subarrays at different positions count separately? Yes.

02Brute force

For every start, extend right with a running max/min and count until the spread exceeds limit.

Cost: O(n²) time in the worst case.

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.