LeetCode 2110 - Number of Smooth Descent Periods of a Stock

LeetCode Problem 2110

Difficulty: 🟡 Medium
Topics: Array, Math, Two Pointers, Dynamic Programming, Sliding Window

Solution

Problem Understanding

This problem is asking us to count all "smooth descent periods" in a stock price array. A smooth descent period is defined as a contiguous sequence of days where the stock price decreases by exactly 1 each day, except the first day which is always counted as a valid period of length 1. Essentially, every individual day counts as a period of length 1, and any sequence of consecutive days where the difference between consecutive prices is exactly 1 contributes additional periods.

The input prices is an integer array of size up to 100,000, with each price between 1 and 100,000. The expected output is a single integer representing the total number of smooth descent periods.

Key insights from the constraints include that the array can be large, so a naive O(n²) solution that checks all subarrays will be too slow. Also, all values are positive integers, so we do not need to handle negative prices.

Important edge cases include arrays of length 1, arrays with constant prices, and arrays where no consecutive days decrease by exactly 1.

Approaches

Brute Force

A brute-force approach would involve checking every possible contiguous subarray and verifying if it is a smooth descent period. For each start index i, we would expand to the right while the difference between consecutive elements is exactly 1, counting all valid subarrays. This approach guarantees correctness but is too slow for large arrays because it has O(n²) time complexity.

Optimal

The key observation for an optimal solution is that smooth descent periods are consecutive sequences, and the number of periods in a sequence of length k is given by the sum of the first k integers. Instead of enumerating all subarrays, we can iterate through the array once, maintaining a running count of the current descent length. For each day, if prices[i-1] - prices[i] == 1, we extend the current sequence; otherwise, we reset the sequence. At each step, the number of smooth descent periods ending on that day is equal to the length of the current sequence. Summing these counts gives the total number of periods.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check all subarrays explicitly
Optimal	O(n)	O(1)	Single pass, maintain current descent length

Algorithm Walkthrough

1. Initialize total_periods to 0 to store the cumulative count of smooth descent periods.
2. Initialize current_length to 1, representing the descent period length ending at the first day.
3. Iterate through the array from index 1 to n-1.
4. For each index i, check if prices[i-1] - prices[i] == 1.

• If true, increment current_length by 1.
• Otherwise, reset current_length to 1, as the descent period has broken.

5. Add current_length to total_periods at each iteration, because every day contributes as the end of multiple periods.
6. Return total_periods after finishing the iteration.

Why it works: This algorithm works because the number of descent periods ending at each day is exactly equal to the length of the current descending sequence. Adding these counts ensures all subarrays are counted efficiently without explicitly enumerating them.

Python Solution

from typing import List

class Solution:
    def getDescentPeriods(self, prices: List[int]) -> int:
        total_periods = 1  # first day is always a period
        current_length = 1
        
        for i in range(1, len(prices)):
            if prices[i-1] - prices[i] == 1:
                current_length += 1
            else:
                current_length = 1
            total_periods += current_length
        
        return total_periods

In this Python implementation, we start by counting the first day as a valid period. As we iterate through the array, current_length tracks the length of the current smooth descent. Every time we move to the next day, we either extend the sequence if the difference is 1, or reset if it is not. Adding current_length to total_periods ensures all subarrays ending at that day are counted.

Go Solution

func getDescentPeriods(prices []int) int64 {
    totalPeriods := int64(1) // first day is always a period
    currentLength := 1
    
    for i := 1; i < len(prices); i++ {
        if prices[i-1] - prices[i] == 1 {
            currentLength++
        } else {
            currentLength = 1
        }
        totalPeriods += int64(currentLength)
    }
    
    return totalPeriods
}

In Go, we need to use int64 to avoid integer overflow for large arrays and counts. The logic mirrors the Python implementation, iterating over the array and updating currentLength and totalPeriods accordingly.

Worked Examples

Example 1: [3,2,1,4]

i	prices[i]	current_length	total_periods
0	3	1	1
1	2	2	3
2	1	3	6
3	4	1	7

Output: 7

Example 2: [8,6,7,7]

i	prices[i]	current_length	total_periods
0	8	1	1
1	6	1	2
2	7	1	3
3	7	1	4

Output: 4

Example 3: [1]

i	prices[i]	current_length	total_periods
0	1	1	1

Output: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the prices array
Space	O(1)	Only a few integer variables are used, no extra data structures

The complexity is optimal for the input constraints. No additional memory is needed, and each element is processed once.

Test Cases

# Provided examples
assert Solution().getDescentPeriods([3,2,1,4]) == 7  # example 1
assert Solution().getDescentPeriods([8,6,7,7]) == 4  # example 2
assert Solution().getDescentPeriods([1]) == 1        # example 3

# Edge and stress tests
assert Solution().getDescentPeriods([1,2,3,4,5]) == 5  # increasing sequence
assert Solution().getDescentPeriods([5,4,3,2,1]) == 15 # decreasing by 1 all the way
assert Solution().getDescentPeriods([1,1,1,1]) == 4    # constant sequence
assert Solution().getDescentPeriods([100000]) == 1     # single large value
assert Solution().getDescentPeriods([2,1,2,1,2,1]) == 6 # alternating descents

Test	Why
[3,2,1,4]	Validates a mixed sequence with a full descent
[8,6,7,7]	Validates that non-1 differences reset descent
[1]	Single-element array
[1,2,3,4,5]	Strictly increasing sequence
[5,4,3,2,1]	Continuous smooth descent of maximum length
[1,1,1,1]	Constant prices
[100000]	Maximum single element
[2,1,2,1,2,1]	Alternating descent sequences

Edge Cases

One important edge case is an array of length 1. The algorithm correctly counts this as one smooth descent period. Another edge case is a strictly increasing array, which should count only single-day periods; the algorithm resets current_length each time, handling this correctly. A third edge case is a large array with a long descending sequence; using int64 in Go prevents integer overflow for large sums, and in Python the arbitrary-precision integers handle it natively. Arrays with repeating numbers also require correct resetting, which is managed by checking prices[i-1] - prices[i] == 1.