Stock Span Problem
You get the closing price of a stock on each day: prices[i] is the price on day i. The span of day i is the number of days in a row, ending with day i and counting it, on which the price was less than or equal to prices[i].
Return every day's span, in the same order as prices. Every span is at least 1, because a day always counts itself.
Function
- pricesinteger-array
- the price on each day, in order
- Returnsinteger-array
- the span of every day, in the same order
Constraints
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- An earlier day with the same price counts toward the span; only a strictly higher price stops it.
Examples
- Input
- prices = [31, 27, 14, 21, 30, 18, 40]
- Output
- [1, 1, 1, 2, 4, 1, 7]
- Explanation
- Day 3 at 21 reaches back over 14 and stops at 27: span 2. Day 4 at 30 stops at 31: span 4. Day 6 at 40 tops every earlier price and covers all 7 days.
- Input
- prices = [8, 8, 3, 8]
- Output
- [1, 2, 1, 4]
- Explanation
- Equal prices count, so day 1 at 8 covers day 0 and gets 2. Day 3 at 8 covers the 3 and both earlier 8s, a span of 4.
- Input
- prices = [50, 40, 30, 20]
- Output
- [1, 1, 1, 1]
- Explanation
- Every day is cheaper than the day before it, so no span reaches back past the day itself and every span is 1.
Follow-up
Prices now arrive one at a time, and you must report each span as its price comes in. Which approach still works, and what does it keep between calls?
Hints
Open them one at a time. Each one gives away a little more.
Counting backward from every day repeats work: on 8000 days at the same price, the last day alone walks back 8000 days. When you walk back from today, which earlier days can you skip for good?
Once today's price is at least as high as some earlier day, that earlier day can never be the one that stops a later span: today is closer and at least as expensive. Only the days that are more expensive than everything after them still matter, and their prices fall from oldest to newest.
Walk the days in order and keep the earlier days that still matter on a stack, as indices. Before you answer for today, pop every day whose price is at most today's. An empty stack means the span reaches back to day 0; otherwise it stops one day after the day left on top. Then push today.
Solution
The span of a day ends at the nearest earlier day with a strictly higher price. Walking back to find it costs up to n steps per day. Instead, keep only the days that can still stop a future span: a stack of indices with strictly falling prices finds every boundary in one pass.
Count backward from every day
Correct, but does not finish on the largest tests
Intuition
Follow the definition. For day i, step back one day at a time while the price there is at most prices[i], counting day i too. The first strictly higher price, or the start of the array, ends the run.
No walk reuses an earlier one. On flat or rising prices every walk runs back to day 0: n = 10^4 days means about 5 × 10^7 steps.
Algorithm
- Make
span, an array as long asprices. - For each day
i, set a counter to 0 and a pointerjtoi. - While
j ≥ 0andprices[j] ≤ prices[i], add 1 to the counter and movejone day back. - Store the counter in
span[i]. After the last day, returnspan.
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanMonotonic stack of higher days
Intuition
Call the nearest earlier day with a strictly higher price the blocker. The span is today - blocker, or today + 1 when there is none.
In the first example, day 3 costs 21 and day 4 costs 30. Every later walk reaches day 4 first, and any price that gets past 30 also gets past 21, so day 3 can never block again. In general, when today arrives, every earlier candidate priced at most today's price is finished: pop it. The day left on top is today's blocker. Then push today.
The stack's prices strictly fall from bottom to top, so the first one that survives is the nearest higher price. In the first example, day 4 pops days 3 and 1 and stops at day 0, for a span of 4 - 0 = 4. Each day is pushed once and popped at most once, so the pass runs in O(n).
Algorithm
- Make the
spanarray and an empty stack for day indices. - For each day
today, pop indices from the stack while their price is less than or equal toprices[today]. - If the stack is empty, the span is
today + 1; otherwise it istodayminus the index on top. - Push
todayand move to the next day. Returnspan.
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
Pitfalls and edge cases
- Popping on
<instead of<=. In[8, 8, 3, 8]the last day has a span of 4; stopping at the earlier 8 gives 2. - Writing
todayinstead oftoday + 1when the stack is empty. Day 0 must get 1, not 0. - Popping only once per day. In the first example 40 has to clear days 5, 4 and 0. Stop after day 5 and day 4 looks like its blocker, for a span of 2 instead of 7.
- In Lua and R, arrays start at 1. With 1-based indices the empty-stack span is
today, nottoday + 1.
Frequently asked questions4
What is the time complexity of the stock span problem?
O(n) time and O(n) extra space with the monotonic stack, since a day leaves the stack at most once. Walking backward from every day is O(n²) when prices keep rising or stay flat.
Should the stack store prices or day indices?
Day indices. The span is a count of days, and only the blocker's index gives you that. prices[index] reads the price back for the comparison.
Can the stock span problem be solved without a separate stack?
Yes. Start at j = today - 1; while j ≥ 0 and prices[j] ≤ prices[today], jump to j - span[j], since every day inside that span is priced at most prices[j]. The span is today - j. The jumps land only on days the stack would hold, so the pass stays O(n).
Is the stock span problem a previous greater element problem?
Yes, measured in days: for each day you find the nearest earlier day with a strictly higher price and report how far back it is. Flip the scan direction or the comparison and the same stack gives next greater, next smaller or previous smaller.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def stockSpan(prices):
# Write code hereTest #1
Test #2
Test #3
Argument
prices = [31, 27, 14, 21, 30, 18, 40]
Expected Output
[1, 1, 1, 2, 4, 1, 7]