The span of a stock's price on day i is the number of consecutive days up to and including day i on which the price was less than or equal to the price on day i.
Given the daily prices arr, return the span for each day.
<= today's price, so the span reaches the very start: i + 1.< instead of <=, so equal prices end the span.Input: arr = [100,80,60,70,60,75,85] Output: [1,1,1,2,1,4,6] Each day's span reaches back to the previous day with a strictly higher price.
Input: arr = [10,4,5,90,120,80] Output: [1,1,2,4,5,1] Day with price 120 spans all 5 prior days; 80 (last) has span 1 because 120 > 80.
- 1 <= arr.length <= 10^5 - 1 <= arr[i] <= 10^5
A day's span reaches back until it hits a day with a strictly greater price. So the span is i - (index of previous greater price). A monotonic decreasing stack of indices finds that previous-greater boundary for every day in a single O(n) pass.
“Does the span include today?”
Yes — the minimum span is 1 (today itself).
“Less-than-or-equal, or strictly less?”
The span counts days with price <= today's, so it stops at a strictly greater price.
The span of day i reaches back until a day with a strictly greater price stops it.
So span[i] = i minus the index of the previous greater price.
I keep a decreasing-price index stack, pop days not greater than today, and read the boundary off the top.
Worked example — arr = [100, 80, 60, 70, 60, 75, 85]
day 0 (100): span 1 day 1 (80): span 1 (100 > 80) day 2 (60): span 1 day 3 (70): span 2 (60 <= 70, then 80 > 70) day 4 (60): span 1 day 5 (75): span 4 (60,70,60 <= 75, then 80 > 75) day 6 (85): span 6 answer: [1, 1, 1, 2, 1, 4, 6]
Consecutive days at or below today's price are within the span; the first strictly greater earlier price ends it. So span[i] = i - prevGreater(i).
Popping days with price <= arr[i] leaves the nearest earlier greater price on top — the boundary.
Each day is pushed and popped once, so the whole computation is O(n) despite the inner while-loop.
| Walk back per day | Monotonic stack | |
|---|---|---|
| Idea | Count backward while prices are <= | Decreasing index stack; span = i - prevGreater |
| Time | O(n^2) | O(n) |
| Space | O(1) | O(n) |
Full code is in the Approaches selector below.
Key takeaway
span[i] = i - (previous strictly-greater price index), or i + 1 if there's none. A monotonic decreasing-price index stack finds that boundary in one O(n) pass — pop days <= arr[i], read the top.
stack = []
for i in 0 .. n-1:
while stack and arr[stack.top] <= arr[i]: pop
span[i] = stack ? i - stack.top : i + 1
push i
return span