2110. Number of Smooth Descent Periods of a Stock

Problem Statement

You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the ith day.

A smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule[citation:5].

Return the number of smooth descent periods.

Key Insight

The solution relies on these crucial observations:

1. Every single day is a valid smooth descent period by definition (length 1 periods)
2. For contiguous days where each day's price is exactly one less than the previous day, all subarrays of that contiguous segment are valid smooth descent periods
3. If we find a contiguous segment of length L where prices decrease by exactly 1 each day, it contributes L * (L + 1) / 2 smooth descent periods
4. The array can be divided into multiple such segments separated by "breaks" where the difference is not exactly 1
5. We can process the array in one pass using a sliding window or counter approach

Approach 1: Sliding Window / Counter (Optimal)

This is the most efficient approach with O(n) time and O(1) space[citation:1]. We maintain a counter that tracks the length of the current smooth descent segment.

Algorithm Steps

1. Initialize ans = 1 (for the first day) and dp = 1 (current descent length)
2. Iterate from day 1 to n-1:
   • If prices[i] == prices[i-1] - 1, increment dp (extend current descent)
   • Otherwise, reset dp = 1 (start new descent)
   • Add dp to ans (all subarrays ending at current day)
3. Return ans

How It Works

At each position i, dp represents the number of smooth descent periods ending at day i. When we extend a descent, all previous periods that ended at i-1 can be extended to include i, plus the new single-day period at i.

Complexity Analysis

Where n is the number of days (length of prices array). Single pass through the array with constant extra space[citation:1].

class Solution {
public:
  long long getDescentPeriods(vector<int>& prices) {
    long long ans = 1;  // prices[0]
    int dp = 1;

    for (int i = 1; i < prices.size(); ++i) {
      if (prices[i] == prices[i - 1] - 1)
        ++dp;
      else
        dp = 1;
      ans += dp;
    }

    return ans;
  }
};

class Solution {
  public long getDescentPeriods(int[] prices) {
    long ans = 1; // prices[0]
    int dp = 1;

    for (int i = 1; i < prices.length; ++i) {
      if (prices[i] == prices[i - 1] - 1)
        ++dp;
      else
        dp = 1;
      ans += dp;
    }

    return ans;
  }
}

class Solution:
    def getDescentPeriods(self, prices: list[int]) -> int:
        ans = 1  # prices[0]
        dp = 1

        for i in range(1, len(prices)):
            if prices[i] == prices[i - 1] - 1:
                dp += 1
            else:
                dp = 1
            ans += dp

        return ans

Approach 2: Mathematical Formula for Contiguous Segments

Find all maximal smooth descent segments and use the formula for the sum of 1 + 2 + ... + L = L(L+1)/2 for each segment[citation:5].

Algorithm Steps

1. Initialize ans = 0 and i = 0
2. While i < n:
   • Start new segment with length L = 1
   • Move i to next day
   • While still in smooth descent (prices[i-1] - prices[i] == 1), increment L and i
   • Add L * (L + 1) / 2 to answer
3. Return ans

How It Works

A contiguous segment of length L where prices decrease by exactly 1 each day contains exactly L single-day periods, L-1 two-day periods, ..., and 1 L-day period. The total is the sum of 1 to L, which equals L(L+1)/2.

Complexity Analysis

Single pass through the array with constant extra space[citation:5].

class Solution {
public:
    long long getDescentPeriods(vector<int>& prices) {
        int n = prices.size();
        long long ans = 0, i = 0;
        while (i < n) {
            long long l = 1;
            i++;
            while (i < n && prices[i - 1] - prices[i] == 1) i++, l++;
            ans += (l + 1) * l / 2;
        }
        return ans;
    }
};

class Solution {
    public long getDescentPeriods(int[] prices) {
        int n = prices.length;
        long ans = 0, i = 0;
        while (i < n) {
            long l = 1;
            i++;
            while (i < n && prices[i - 1] - prices[i] == 1) {
                i++;
                l++;
            }
            ans += (l + 1) * l / 2;
        }
        return ans;
    }
}

class Solution:
    def getDescentPeriods(self, prices: list[int]) -> int:
        n = len(prices)
        ans = 0
        i = 0
        while i < n:
            l = 1
            i += 1
            while i < n and prices[i - 1] - prices[i] == 1:
                i += 1
                l += 1
            ans += (l + 1) * l // 2
        return ans

Approach 3: Dynamic Programming (Full DP Array)

Traditional dynamic programming approach storing DP values for each day[citation:5].

Algorithm Steps

1. Initialize dp array of size n with all 1's (each day is a valid period)
2. Initialize ans = 0
3. For each day i from 0 to n-1:
   • If i > 0 and prices[i-1] - prices[i] == 1, add dp[i-1] to dp[i]
   • Add dp[i] to ans
4. Return ans

How It Works

dp[i] stores the number of smooth descent periods ending at day i. If day i continues a smooth descent from day i-1, then all periods ending at i-1 can be extended to include i.

Complexity Analysis

Single pass through the array but requires O(n) space for the DP array[citation:5].

class Solution {
public:
    long long getDescentPeriods(vector<int>& prices) {
        int n = prices.size();
        long long ans = 0;
        vector<int> dp(n, 1);
        for (int i = 0; i < n; i++) {
            if (i > 0 && prices[i - 1] - prices[i] == 1) {
                dp[i] += dp[i - 1];
            }
            ans += dp[i];
        }
        return ans;
    }
};

class Solution {
    public long getDescentPeriods(int[] prices) {
        int n = prices.length;
        long ans = 0;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            if (i > 0 && prices[i - 1] - prices[i] == 1) {
                dp[i] += dp[i - 1];
            }
            ans += dp[i];
        }
        return ans;
    }
}

class Solution:
    def getDescentPeriods(self, prices: list[int]) -> int:
        n = len(prices)
        ans = 0
        dp = [1] * n
        for i in range(n):
            if i > 0 and prices[i - 1] - prices[i] == 1:
                dp[i] += dp[i - 1]
            ans += dp[i]
        return ans

Detailed Example Walkthrough

Let's trace through the sliding window approach with prices = [3,2,1,4]:

Comparison of Approaches

Edge Cases and Testing

1. Single Element Array

Input: [5] → Output: 1
Input: [1] → Output: 1
All single-element arrays should return 1

2. All Smooth Descent

Input: [5,4,3,2,1] → Output: 15
Length 5: contributes 5*6/2 = 15 periods
[5],[4],[3],[2],[1],[5,4],[4,3],[3,2],[2,1],[5,4,3],[4,3,2],[3,2,1],[5,4,3,2],[4,3,2,1],[5,4,3,2,1]

3. No Smooth Descent (Except Single Days)

Input: [1,3,5,7,9] → Output: 5
Each day is its own period, no multi-day periods
[1],[3],[5],[7],[9]

4. Mixed Pattern

Input: [8,7,6,8,7,6,5] → Output: 13
Segments: [8,7,6] (length 3 → 6 periods), [8,7,6,5] (length 4 → 10 periods)
But careful: Actually two separate segments: [8,7,6] and [8,7,6,5] starting at index 3
Total: 6 + (10-3) = 13? Let's compute properly:
Using sliding window: 1+2+3+1+2+3+4 = 16? Wait, recalculate:
Actually trace it: 1,2,3,1,2,3,4 → sum = 16

5. Large Arrays

Input: [100000,99999,99998,...,1] (length 100000)
Output: 100000*100001/2 = 5,000,050,000
Must use 64-bit integers (long long in C++, long in Java)

FAQs