# Number of Smooth Descent Periods of a Stock
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-smooth-descent-periods-of-a-stock)
Canonical: https://scaleengineer.com/dsa/problems/number-of-smooth-descent-periods-of-a-stock
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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
## Brute Force Approach
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Dynamic Programming with Space Optimization
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public long getDescentPeriods(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        long totalPeriods = 0;
        int currentStreak = 0;
        
        for (int i = 0; i < prices.length; i++) {
            if (i > 0 && prices[i - 1] - prices[i] == 1) {
                // The streak continues, so we increment its length.
                currentStreak++;
            } else {
                // A new streak starts (or the first day).
                currentStreak = 1;
            }
            // Add the number of periods ending at the current day to the total.
            totalPeriods += currentStreak;
        }
        
        return totalPeriods;
    }
}
```
### Algorithm
1. Initialize a `long` variable `totalPeriods` to 0 to store the final result.
2. Initialize an integer `currentStreak` to 0. This variable will track the length of the current continuous smooth descent period ending at the current index.
3. Iterate through the `prices` array from left to right with an index `i`.
4. For each element `prices[i]`, compare it with the previous element `prices[i-1]`.
5. If `i > 0` and `prices[i-1] - prices[i] == 1`, it means the current day extends the smooth descent period. Increment `currentStreak`.
6. Otherwise (if `i == 0` or the condition is not met), the streak is broken or a new one is starting. Reset `currentStreak` to 1.
7. 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`.
8. 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`.

# Solutions
### Java

```java
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 ; } }
```

### CPP

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

### Python

```python
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
```