Scale Engineer

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
MathDynamic 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 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.

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 ≠ 1.

Example 3:

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

 

Constraints:

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

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

  1. Initialize a long variable count to 0.
  2. Get the length of the array, n.
  3. Start an outer loop with index i from 0 to n-1. This index represents the start of a potential subarray.
  4. 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.
  5. For each subarray prices[i...j], we need to check if it's a smooth descent period.
  6. If j == i, the subarray has one element, which is always a smooth descent period. Increment count.
  7. 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.
  8. 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.
  9. 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.
  10. 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.

class Solution {    public long getDescentPeriods(int[] prices) {        long count = 0;        int n = prices.length;        for (int i = 0; i < n; i++) {            // The inner loop starts from i and checks for smooth descent            for (int j = i; j < n; j++) {                if (j == i) {                    // A single day is always a smooth descent period                    count++;                } else {                    if (prices[j - 1] - prices[j] == 1) {                        // The subarray prices[i...j] is a smooth descent period                        count++;                    } else {                        // The streak is broken, move to the next starting point                        break;                    }                }            }        }        return count;    }}

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.

Solutions

class 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 ; } }

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 →

Next problem