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

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

✓ Brute Force

⏱️ Time: O(n³) Space: O(1)

For each starting position, check all possible ending positions to see if the subarray forms a valid smooth descent period where each element is exactly 1 less than the previous.

Dynamic Programming

⏱️ Time: O(n) Space: O(1)

Instead of checking all subarrays, we iterate once through the array. For each position, we track how long the current descent period is. If a descent of length n ends at position i, it contributes n subarrays to the total count.

Brute Force — Algorithm Steps

Start from each index i
For each starting position, extend to all possible ending positions j
Check if subarray [i...j] forms a valid smooth descent
Count all valid subarrays

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Check every possible contiguous subarray

Validate Descent

For each subarray, verify it forms a valid descent

Count Valid

Count all subarrays that satisfy the descent condition

Code -

solution.c — C

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

int solution(int* prices, int n) {
    int count = 0;
    
    // Check all possible subarrays
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Check if subarray [i...j] is a valid descent period
            int valid = 1;
            for (int k = i + 1; k <= j; k++) {
                if (prices[k] != prices[k - 1] - 1) {
                    valid = 0;
                    break;
                }
            }
            if (valid) {
                count++;
            }
        }
    }
    
    return count;
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

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³)

Three nested loops: n starting positions × n ending positions × n validation time

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ 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

Number of Smooth Descent Periods of a Stock - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler