Number of Smooth Descent Periods of a Stock

Medium
1372.

Number of Smooth Descent Periods of a Stock

Number of Smooth Descent Periods of a Stock is a medium coding problem on arrays, dynamic programming and math, asked in Amazon and Google interviews.

prices[i] is a stock's price on day i.

A smooth descent period is a run of one or more consecutive days in which each day's price is exactly 1 lower than the previous day's. The first day of a period is unrestricted, so every single day is a smooth descent period on its own.

Return the number of smooth descent periods.

CodeKairo note: the original allows prices.length up to 10^5 and returns a 64-bit count; here the length is at most 5 * 10^4, so the answer fits in a 32-bit integer.

Example 1

Input
prices = [5,4,3,7,6]
Output
9
Explanation
Five single days, `[5,4]`, `[4,3]`, `[5,4,3]` and `[7,6]`.

Example 2

Input
prices = [9,7,8,8]
Output
4
Explanation
No two neighbours differ by exactly 1 downward, so only the four single days count.

Example 3

Input
prices = [10]
Output
1

Constraints

  • 1 <= prices.length <= 5 * 10^4
  • 1 <= prices[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} prices
 * @return {number}
 */
var getDescentPeriods = function(prices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Smooth Descent Periods of a Stock — Solution

Number of Smooth Descent Periods of a Stock solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Smooth Descent Periods of a Stock is a medium coding problem on arrays, dynamic programming and math, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming, Math
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

prices[i] is a stock's price on day i.

A smooth descent period is a run of one or more consecutive days in which each day's price is exactly 1 lower than the previous day's. The first day of a period is unrestricted, so every single day is a smooth descent period on its own.

Return the number of smooth descent periods.

CodeKairo note: the original allows prices.length up to 10^5 and returns a 64-bit count; here the length is at most 5 * 10^4, so the answer fits in a 32-bit integer.

Example 1

Input: prices = [5,4,3,7,6]
Output: 9
Explanation: Five single days, `[5,4]`, `[4,3]`, `[5,4,3]` and `[7,6]`.

Example 2

Input: prices = [9,7,8,8]
Output: 4
Explanation: No two neighbours differ by exactly 1 downward, so only the four single days count.

Example 3

Input: prices = [10]
Output: 1

Constraints

  • 1 <= prices.length <= 5 * 10^4
  • 1 <= prices[i] <= 10^5

Hints for Number of Smooth Descent Periods of a Stock

  1. Hint 1

    A period is valid exactly when every adjacent pair inside it steps down by 1, so the valid periods live inside maximal "descending by 1" runs.

  2. Hint 2

    Count the periods by their last day: how many valid periods end at day i?

  3. Hint 3

    If day i continues the run (prices[i] == prices[i-1] - 1) the count is one more than for day i - 1; otherwise it is 1. Sum these counts.

How to solve Number of Smooth Descent Periods of a Stock

Count periods by their last day. The number of valid periods ending at day i is the length of the descending-by-one run that ends there.

Approach

  1. Keep run, the length of the current smooth run ending at the previous day, and a total.
  2. For each day i: if i > 0 and prices[i] == prices[i-1] - 1, increment run; otherwise set run = 1.
  3. Add run to the total — that many periods end at day i (starting at any day inside the run).
  4. Return the total.

Why it works

A period [j, i] is smooth exactly when every step inside it is a drop of 1, i.e. when j lies within the maximal smooth run ending at i. There are exactly run such start days, and summing over i counts each period once by its last day. Equivalently, a maximal run of length L contributes L(L+1)/2.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The drop must be exactly 1 — a drop of 2 or an equal price breaks the run.
  • Single days always count, so the answer is at least n.
  • The total grows quadratically on a long run — accumulate in 64-bit in fixed-width languages.

Reference solution

Python

from typing import List

def getDescentPeriods(prices: List[int]) -> int:
    total = 0
    run = 0
    for i, p in enumerate(prices):
        if i > 0 and p == prices[i - 1] - 1:
            run += 1
        else:
            run = 1
        total += run
    return total

Java

public static int getDescentPeriods(int[] prices) {
    long total = 0;
    int run = 0;
    for (int i = 0; i < prices.length; i++) {
        if (i > 0 && prices[i] == prices[i - 1] - 1) run++;
        else run = 1;
        total += run;
    }
    return (int) total;
}

C++

int getDescentPeriods(vector<int>& prices) {
    long long total = 0;
    int run = 0;
    for (int i = 0; i < (int) prices.size(); i++) {
        if (i > 0 && prices[i] == prices[i - 1] - 1) run++;
        else run = 1;
        total += run;
    }
    return (int) total;
}

JavaScript

var getDescentPeriods = function(prices) {
    var total = 0, run = 0;
    for (var i = 0; i < prices.length; i++) {
        if (i > 0 && prices[i] === prices[i - 1] - 1) run++;
        else run = 1;
        total += run;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming