#2110

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Smooth Descent Periods of a Stock

Count all contiguous periods where stock prices descend smoothly by exactly one using dynamic programming techniques.

Problem Statement

You are given an array of integers representing daily stock prices. A smooth descent period is defined as one or more consecutive days where each day's price is exactly one less than the previous day's price, except for the first day of the period which can be any value.

Return the total number of smooth descent periods present in the given array. Single-day periods count as smooth descent periods, and longer periods are formed by consecutive decreasing values of exactly one.

Examples

Example 1

Input: prices = [3,2,1,4]

Output: 7

There are 7 smooth descent periods: [3], [2], [1], [4], [3,2], [2,1], and [3,2,1] Note that a period with one day is a smooth descent period by the definition.

Example 2

Input: prices = [8,6,7,7]

Output: 4

There are 4 smooth descent periods: [8], [6], [7], and [7] Note that [8,6] is not a smooth descent period as 8 - 6 ≠ 1.

Example 3

Input: prices = [1]

Output: 1

There is 1 smooth descent period: [1]

Constraints

1 <= prices.length <= 105
1 <= prices[i] <= 105

Solution Approach

Dynamic Programming Tracking

Use a variable to track the length of the current smooth descent period. Initialize count with 1 for the first day. For each subsequent price, check if the difference from the previous price is exactly 1. If so, increment the period length; otherwise, reset to 1.

Accumulate Total Periods

For each day, add the current smooth descent period length to the total count. This captures all sub-periods ending at that day, including single-day periods, ensuring correct accumulation.

Iterative One-Pass Optimization

Iterate once through the array, updating both the current period length and total count. This maintains O(n) time and O(1) space complexity, avoiding unnecessary storage of subarrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since we iterate through the prices array once. Space complexity is O(1) because we only track current period length and total count without storing intermediate periods.

What Interviewers Usually Probe

Focuses on consecutive differences of exactly 1 in array sequences.
Expect candidates to handle single-day periods correctly.
Wants an O(n) one-pass solution without extra arrays.

Common Pitfalls or Variants

Common pitfalls

Resetting the period length incorrectly when difference is not exactly 1.
Forgetting to include single-day periods in the total count.
Miscounting overlapping sub-periods within longer smooth descent sequences.

Follow-up variants

Count smooth ascent periods where each day's price increases by 1.
Calculate maximum length of any smooth descent period instead of total count.
Handle circular arrays where the end connects back to the start for smooth descent.

FAQ

What is a smooth descent period in this stock problem?

It is a contiguous sequence of days where each day's price is exactly one less than the previous, with single-day periods included.

How does dynamic programming apply to this problem?

Dynamic programming tracks the length of the current smooth descent period and accumulates counts, using state transitions from previous day periods.

Can smooth descent periods overlap?

Yes, longer periods contain multiple sub-periods that overlap; each sub-period contributes to the total count.

What is the optimal time complexity for this problem?

A one-pass O(n) solution is optimal, tracking current period length and total count without extra arrays.

How do single-day periods affect the total count?

Every single day counts as a smooth descent period by definition, so each day adds at least one to the total count.

terminal

Solution

Solution 1: Two Pointers

We define an answer variable $\textit{ans}$ with an initial value of $0$.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#2019 the score of students solving math expression #1994 the number of good subsets #1872 stone game viii