Number of Smooth Descent Periods of a Stock

Number of Smooth Descent Periods of a Stock - Problem

Array Math Two Pointers Dynamic Programming Sliding Window Medium

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.

Input & Output

Example 1 — Basic Descent

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

› Output: 7

💡 Note: Smooth descent periods: [3], [2], [1], [4], [3,2], [2,1], [3,2,1]. Each single element forms a period, plus [3,2] (3→2 drops by 1), [2,1] (2→1 drops by 1), and [3,2,1] (both transitions drop by 1).

Example 2 — No Multi-Element Descents

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

› Output: 4

💡 Note: Only single-element periods: [8], [6], [7], [7]. No multi-element descents since 8→6 drops by 2 (not 1), 6→7 increases, 7→7 stays same.

Example 3 — Long Descent

$ Input: prices = [1]

› Output: 1

💡 Note: Single element [1] forms one descent period.

Constraints

1 ≤ prices.length ≤ 10⁵
1 ≤ prices[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of stock prices: [3,2,1,4]

Find Descents

Identify all valid smooth descent periods

Count Total

Return total number of descent periods: 7

Key Takeaway

🎯 Key Insight: A descent of length n contributes exactly n subarrays to the total count

Asked in

G Google 25 a Amazon 18 f Facebook 15 M Microsoft 12

The key insight is that if we have a descent of length n ending at position i, it contributes exactly n subarrays to the total count. The optimal approach uses dynamic programming to track current descent length in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(n)	O(1)	Track the length of current descent period and accumulate count efficiently
Brute Force	O(n³)	O(1)	Check all possible subarrays to see if they form valid descent periods

Dynamic Programming — Algorithm Steps

Initialize count and current descent length
For each position, check if it continues the descent
If descent continues, increment length; otherwise reset to 1
Add current descent length to total count

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with length=1, count=0

Process Each Element

Check if current element continues descent or starts new one

Add to Count

Add current descent length to total count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* prices, int n) {
    if (n == 0) {
        return 0;
    }
    
    int count = 0;
    int currentLength = 1; // Every single element forms a descent period
    
    for (int i = 0; i < n; i++) {
        if (i > 0 && prices[i] == prices[i - 1] - 1) {
            // Continue the descent period
            currentLength++;
        } else {
            // Start a new descent period
            currentLength = 1;
        }
        
        // Add the number of subarrays ending at position i
        count += currentLength;
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int prices[1000];
    int n = 0;
    char* ptr = strchr(line, '[');
    ptr++;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        prices[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(prices, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array, each element processed once

✓ Linear Growth

Space Complexity

O(1)

Only using two variables to track count and current descent length

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler