Sums of Staircase Runs

Medium

Call a piece of an array a **staircase** if every next element is exactly 1 greater than the previous one, or every next element is exactly 1 smaller. A one-element piece is a staircase too. Given an array values, add up the elements of every staircase piece (contiguous subarray) together. The answer can be large, so return it modulo 10⁹ + 7. Enumerating all pieces is too slow; aim for O(n).

Example 1

values=[4, 5, 6] → 50

The fitting pieces are [4], [5], [6], [4, 5], [5, 6], [4, 5, 6]. Their sums: 4 + 5 + 6 + 9 + 11 + 15 = 50.

Example 2

values=[3, 2, 2, 3] → 20

Besides single elements (total 10), [3, 2] (step −1) and [2, 3] (step +1) fit: 10 + 5 + 5 = 20. [2, 2] does not, its step is 0.

Example 3

values=[10, 30] → 40

Only single elements fit: 10 + 30 = 40.

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Dynamic Programming

Similar problems

Longest Ridge on the Route Medium Word Growth Chain Medium Spells Without Neighbors Medium Erasable Marked Letters Medium Water Between Walls Hard

Input

values=[4, 5, 6]

Expected

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