Show problems as
Classic problem #413MediumArrayDynamic ProgrammingSliding Window

Arithmetic Slices

Real-world version: Steady-Gradient Stretches
Tracked in this browser only
Read Arithmetic Slices on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A trail is surveyed at evenly spaced markers, and heights[i] is the elevation at marker i.

A stretch is a contiguous run of markers heights[i] through heights[j]. A stretch is steady when it covers at least three markers and the elevation change between each pair of neighbouring markers inside it is the same. The shared change may be positive, negative or zero.

Return how many steady stretches the trail has. Two stretches are different when they start at different markers or end at different markers, even if their elevations match.

Examples

Example 1

Input
heights = [3, 6, 9, 12]
Output
3

Every neighbouring pair rises by 3. The stretches covering at least three markers are markers 0 to 2, markers 1 to 3 and markers 0 to 3.

Example 2

Input
heights = [1, 2, 4, 8]
Output
0

The three changes are 1, 2 and 4. No stretch of three or more markers has one repeated change.

Example 3

Input
heights = [5, 5, 5, 5]
Output
3

The trail is flat, so every change is 0 and the stretches markers 0 to 2, 1 to 3 and 0 to 3 are all steady.

Constraints

  • 1 <= heights.length <= 5000
  • -1000 <= heights[i] <= 1000
  • The answer is at most 1.3 * 10^7.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_steady_stretches(heights: list[int]) -> int:
Java
public int countSteadyStretches(int[] heights)

More on the same topics