Price Run Lengths
MediumStack
Problem
A trader logs the closing price of a share each day in prices. For every day, she wants its run length: the number of consecutive days ending on that day (counting the day itself) whose price was less than or equal to that day's price.
Return the run length for every day.
Example 1
- Input:
- prices = [60, 55, 58, 62, 50, 62]
- Output:
- [1, 1, 2, 4, 1, 6]
Day 3 (62) covers 55, 58, 60 and itself: 4. The last day (62) covers every day, since 62 ≤ 62.
Example 2
- Input:
- prices = [10, 20, 30]
- Output:
- [1, 2, 3]
Constraints
- 1 ≤ prices.length ≤ 10^5
- 1 ≤ prices[i] ≤ 10^6
Hint
Show the first hint
The run of day i stops at the most recent earlier day with a strictly higher price.
Walkthrough
How to approach it
01Clarify before coding
- Does the run include the day itself? Yes, so every answer is at least 1.
- Equal prices: do they extend the run? Yes, less than or equal counts.
02Brute force
For each day walk backward while prices are ≤ today's price, counting steps.
Cost: O(n²) for steadily rising prices: about 5·10^9 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.