Number of Smooth Descent Periods of a Stock

medium sliding window array run length

Problem

Given an integer array prices where prices[i] is the stock price on day i, a smooth descent period is one or more contiguous days where each day's price is exactly 1 lower than the previous day (the first day is exempt). Return the total number of smooth descent periods.

Inputprices = [3,2,1,4]

Output7

The periods are [3], [2], [1], [4], [3,2], [2,1], [3,2,1]. Each single day counts, plus every longer run that descends by 1.

Inputprices = [8,6,7,7]

Output4

Only the 4 single days qualify; [8,6] fails because 8 − 6 ≠ 1.

prices (comma-separated)

def get_descent_periods(prices):
    total = 0
    cur = 0
    for i in range(len(prices)):
        if i > 0 and prices[i] == prices[i - 1] - 1:
            cur += 1
        else:
            cur = 1
        total += cur
    return total

function getDescentPeriods(prices) {
  let total = 0;
  let cur = 0;
  for (let i = 0; i < prices.length; i++) {
    if (i > 0 && prices[i] === prices[i - 1] - 1) {
      cur += 1;
    } else {
      cur = 1;
    }
    total += cur;
  }
  return total;
}

long getDescentPeriods(int[] prices) {
    long total = 0;
    long cur = 0;
    for (int i = 0; i < prices.length; i++) {
        if (i > 0 && prices[i] == prices[i - 1] - 1) {
            cur += 1;
        } else {
            cur = 1;
        }
        total += cur;
    }
    return total;
}

long long getDescentPeriods(vector<int>& prices) {
    long long total = 0;
    long long cur = 0;
    for (int i = 0; i < (int)prices.size(); i++) {
        if (i > 0 && prices[i] == prices[i - 1] - 1) {
            cur += 1;
        } else {
            cur = 1;
        }
        total += cur;
    }
    return total;
}

Explanation

Instead of listing every smooth descent period, we count them with a single linear pass. The key observation: if a day i ends a descent run of length cur, then it contributes exactly cur new periods — the periods ending at day i of every length from 1 up to cur.

We keep a running cur, the length of the current smooth descent run ending at the day we are looking at. When prices[i] == prices[i-1] - 1 the run extends, so cur += 1. Otherwise the run breaks and a fresh run of length 1 starts, so cur = 1.

After updating cur we add it to total. Because each day contributes the number of valid windows ending there, summing cur over all days gives the total count without ever enumerating the windows themselves.

This is a sliding-window / run-length idea: cur is the length of the window that currently slides forward and grows while the descent-by-1 condition holds, and resets the moment it is violated.

For [3,2,1,4]: cur goes 1, 2, 3, 1 and total accumulates 1, 3, 6, 7 — matching the 7 periods. The algorithm runs in O(n) time and O(1) extra space.

Time: O(n) Space: O(1)