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^41 <= prices[i] <= 10^5
Hints for Number of Smooth Descent Periods of a Stock
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.
Hint 2
Count the periods by their last day: how many valid periods end at day
i?Hint 3
If day
icontinues the run (prices[i] == prices[i-1] - 1) the count is one more than for dayi - 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
- Keep
run, the length of the current smooth run ending at the previous day, and a total. - For each day
i: ifi > 0andprices[i] == prices[i-1] - 1, incrementrun; otherwise setrun = 1. - Add
runto the total — that many periods end at dayi(starting at any day inside the run). - 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 totalJava
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