Number of Smooth Descent Periods of a Stock

Med

#1922Time: O(n^2) - In the worst-case scenario (an array that is entirely a smooth descent, e.g., `[10,9,8,7]`), the inner loop runs `n-i` times for each `i`. This leads to a total number of operations proportional to the sum `n + (n-1) + ... + 1`, which is O(n^2).Space: O(1) - We only use a constant amount of extra space for loop variables and the counter.

Patterns

Math Dynamic Programming

Data structures

Array

Prompt

You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the i^th 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.

Return the number of smooth descent periods.

Example 1:

Input: prices = [3,2,1,4]
Output: 7
Explanation: 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
Explanation: There are 4 smooth descent periods: [8], [6], [7], and [7]
Note that [8,6] is not a smooth descent period as 8 - 6 &ne; 1.

Example 3:

Input: prices = [1]
Output: 1
Explanation: There is 1 smooth descent period: [1]

Constraints:

1 <= prices.length <= 10⁵
1 <= prices[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible contiguous subarray to see if it qualifies as a smooth descent period. It uses nested loops to generate all subarrays starting from each possible index. For each starting index i, it expands the subarray by one element at a time (using index j), and as long as the smooth descent condition (prices[j-1] - prices[j] == 1) is met, it counts the newly formed subarray. If the condition fails, it stops extending from that starting point and moves to the next.

Algorithm

Initialize a long variable count to 0.
Get the length of the array, n.
Start an outer loop with index i from 0 to n-1. This index represents the start of a potential subarray.
Inside the outer loop, start an inner loop with index j from i to n-1. This index represents the end of the potential subarray.
For each subarray prices[i...j], we need to check if it's a smooth descent period.
If j == i, the subarray has one element, which is always a smooth descent period. Increment count.
If j > i, check if the last two elements of the current subarray, prices[j-1] and prices[j], satisfy the condition prices[j-1] - prices[j] == 1.
If they do, it means the subarray prices[i...j] is a valid smooth descent period (since we would have already validated prices[i...j-1] in the previous iteration of the inner loop). Increment count.
If they do not, the smooth descent is broken. Any further extension of the subarray starting at i will also not be smooth. Therefore, we can break out of the inner loop and continue with the next starting index i+1.
After both loops complete, return the total count.

Walkthrough

The algorithm employs two nested loops. The outer loop, indexed by i, iterates from the beginning to the end of the prices array, fixing the starting point of our subarrays. The inner loop, indexed by j, starts from i and extends towards the end of the array. For each subarray prices[i...j], we check for the smooth descent property. A key optimization is that instead of re-validating the entire subarray prices[i...j] every time, we only need to check the newly added element prices[j] against its predecessor prices[j-1]. If prices[j-1] - prices[j] == 1, we know the subarray prices[i...j] is a smooth descent period because we've already confirmed prices[i...j-1] was one in the previous step. If the condition fails, we break the inner loop because no longer subarray starting at i can be a smooth descent period.

1class Solution {2    public long getDescentPeriods(int[] prices) {3        long count = 0;4        int n = prices.length;5        for (int i = 0; i < n; i++) {6            // The inner loop starts from i and checks for smooth descent7            for (int j = i; j < n; j++) {8                if (j == i) {9                    // A single day is always a smooth descent period10                    count++;11                } else {12                    if (prices[j - 1] - prices[j] == 1) {13                        // The subarray prices[i...j] is a smooth descent period14                        count++;15                    } else {16                        // The streak is broken, move to the next starting point17                        break;18                    }19                }20            }21        }22        return count;23    }24}

Complexity

Time

O(n^2) - In the worst-case scenario (an array that is entirely a smooth descent, e.g., `[10,9,8,7]`), the inner loop runs `n-i` times for each `i`. This leads to a total number of operations proportional to the sum `n + (n-1) + ... + 1`, which is O(n^2).

Space

O(1) - We only use a constant amount of extra space for loop variables and the counter.

Trade-offs

Pros

The logic is straightforward and relatively easy to understand, as it directly translates the problem of checking all subarrays into code.

Cons

The time complexity of O(n^2) is inefficient for large inputs as specified in the constraints (n <= 10^5), and will likely lead to a 'Time Limit Exceeded' (TLE) error on most coding platforms.

This optimal approach uses a dynamic programming concept with space optimization. It iterates through the prices array just once, maintaining a count of the length of the current smooth descent streak. The key insight is that if a smooth descent period has a length of k, it contributes k new subarrays that end at the current position. By summing up these counts for each day, we can find the total number of periods in linear time.

Algorithm

Initialize a long variable totalPeriods to 0 to store the final result.
Initialize an integer currentStreak to 0. This variable will track the length of the current continuous smooth descent period ending at the current index.
Iterate through the prices array from left to right with an index i.
For each element prices[i], compare it with the previous element prices[i-1].
If i > 0 and prices[i-1] - prices[i] == 1, it means the current day extends the smooth descent period. Increment currentStreak.
Otherwise (if i == 0 or the condition is not met), the streak is broken or a new one is starting. Reset currentStreak to 1.
The value of currentStreak at any point i is exactly the number of smooth descent periods that end at index i. Add this currentStreak value to totalPeriods.
After iterating through the entire array, totalPeriods will hold the sum of periods ending at each index, which is the total number of smooth descent periods. Return totalPeriods.

Walkthrough

We can solve this problem efficiently in a single pass. We'll maintain a variable, let's call it currentStreak, to keep track of the length of the smooth descent period ending at the current day i.

When we are at day i, we look at the previous day i-1.

If prices[i-1] - prices[i] == 1, the smooth descent continues. This means the current day i can be appended to all smooth descent periods that ended at day i-1. If the streak ending at i-1 had length k, the new streak ending at i has length k+1. So we increment currentStreak.
If the condition is not met (or if i is 0), the streak is broken. A new smooth descent period starts at day i. This period has a length of 1 (just the day i itself). So we reset currentStreak to 1.

At each step i, the value of currentStreak represents the number of smooth descent periods ending at i. For example, if we have [3,2,1] and are at index 2 (value 1), the currentStreak is 3. The periods ending at index 2 are [1], [2,1], and [3,2,1], which is exactly 3 periods. By adding currentStreak to a running total at each step, we accumulate the total count of all possible smooth descent periods.

1class Solution {2    public long getDescentPeriods(int[] prices) {3        if (prices == null || prices.length == 0) {4            return 0;5        }6        7        long totalPeriods = 0;8        int currentStreak = 0;9        10        for (int i = 0; i < prices.length; i++) {11            if (i > 0 && prices[i - 1] - prices[i] == 1) {12                // The streak continues, so we increment its length.13                currentStreak++;14            } else {15                // A new streak starts (or the first day).16                currentStreak = 1;17            }18            // Add the number of periods ending at the current day to the total.19            totalPeriods += currentStreak;20        }21        22        return totalPeriods;23    }24}

Complexity

Time

O(n) - The algorithm involves a single pass through the `prices` array, where `n` is the number of days.

Space

O(1) - Only a few variables are used to store the total count and the current streak length, regardless of the input size.

Trade-offs

Pros

Extremely efficient with O(n) time complexity, allowing it to pass for large inputs.
Optimal space complexity of O(1).

Cons

The logic, while simple once understood, might be slightly less intuitive to derive compared to the direct brute-force method.

Solutions

Solution

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

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

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem