How long this price has held up
A trading widget shows, for each day, how many days back the price has been no higher than it is today — today included.
- Count today and then each earlier consecutive day whose price is less than or equal to today’s.
- Stop at the first earlier day priced above today.
- The first day always answers 1.
price_run(prices: list<int>) → list<int>
Where you start
def price_run(prices: list[int]) -> list[int]:
Worked examples
| Call | Result |
|---|---|
price_run([100, 80, 60, 70, 60, 75, 85]) | [1, 1, 1, 2, 1, 4, 6] |
price_run([10, 20, 30]) | [1, 2, 3] |
price_run([30, 20, 10]) | [1, 1, 1] |
price_run([5, 5, 5]) | [1, 2, 3] |
Hint
Rather than walking backwards each day, keep a stack of earlier days that were priced higher. Popping the ones that were not gives you the run in one pass.
Reference solution in Python
def price_run(prices: list[int]) -> list[int]:
runs = []
higher = []
for i, price in enumerate(prices):
while higher and prices[higher[-1]] <= price:
higher.pop()
runs.append(i + 1 if not higher else i - higher[-1])
higher.append(i)
return runs