Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every contiguous subarray within a run that decreases by exactly one per day is a smooth descent period. A maximal run of length r contains r*(r + 1)/2 such subarrays, including the single-day periods. No valid period crosses a break in the required difference.

Approach

Start a run at the next unprocessed day and extend it while each price equals the previous price minus one. Add the run's triangular count, then begin at the first day after it. Return the sum over all runs. Equal prices and decreases larger than one both end a run; a merely decreasing sequence is not sufficient.

class Solution:
    def getDescentPeriods(self, prices: List[int]) -> int:
        n = len(prices)
        res = 0
        l = 0

        while l < n:
            r = l + 1
            while r < n and prices[r] == prices[r - 1] - 1:
                r += 1
            res += comb(r - l + 1, 2)
            l = r

        return res

Complexity analysis

Let n = prices.length. Time: O(n), because each maximal descent run is scanned once. Auxiliary space: O(1).