We want to find, for each day, how many consecutive days up to and including today had stock prices less than or equal to today's price. We use a stack to remember indices of days with higher prices to quickly jump back.
Analogy: Imagine checking how many consecutive days up to today had cooler or equal weather than today by looking back only at days that were warmer, skipping the cooler ones quickly.
Prices: [100, 80, 60, 70, 60, 75, 85]
Stack stores indices of days with prices higher than current day.
Initial:
Stack: []
Spans: []
Dry Run Walkthrough
Input: prices: [100, 80, 60, 70, 60, 75, 85]
Goal: Calculate span for each day: number of consecutive days up to and including today with price <= current day's price
Step 1: Process day 0 with price 100, stack empty so span is 1, push index 0
Stack: [0]
Spans: [1]
Why: No previous days, so span is 1
Step 2: Process day 1 with price 80, top of stack price 100 > 80, span is 1, push index 1
Stack: [0, 1]
Spans: [1, 1]
Why: Previous day price higher, so span resets to 1
Step 3: Process day 2 with price 60, top stack price 80 > 60, span is 1, push index 2
Stack: [0, 1, 2]
Spans: [1, 1, 1]
Why: Previous day price higher, span is 1
Step 4: Process day 3 with price 70, pop indices 2 (60) because 60 <= 70, top now 1 (80) > 70, span = 3 - 1 = 2, push 3
Stack: [0, 1, 3]
Spans: [1, 1, 1, 2]
Why: Count consecutive days up to day 3 with price <= 70
Step 5: Process day 4 with price 60, top stack price 70 > 60, span is 1, push 4
Stack: [0, 1, 3, 4]
Spans: [1, 1, 1, 2, 1]
Why: Previous day price higher, span resets to 1
Step 6: Process day 5 with price 75, pop indices 4 (60) and 3 (70) because <= 75, top now 1 (80) > 75, span = 5 - 1 = 4, push 5
Stack: [0, 1, 5]
Spans: [1, 1, 1, 2, 1, 4]
Why: Count consecutive days up to day 5 with price <= 75
Step 7: Process day 6 with price 85, pop index 5 (75) because <= 85, top now 1 (80) <= 85, pop 1, top now 0 (100) > 85, span = 6 - 0 = 6, push 6
Stack: [0, 6]
Spans: [1, 1, 1, 2, 1, 4, 6]
Why: Count consecutive days up to day 6 with price <= 85
Result:
Spans: [1, 1, 1, 2, 1, 4, 6]
Annotated Code
DSA Python
class StockSpan:
def calculate_span(self, prices):
n = len(prices)
spans = [0] * n
stack = [] # will store indicesfor i inrange(n):
# Pop indices while current price >= price at stack topwhile stack and prices[stack[-1]] <= prices[i]:
stack.pop()
# If stack empty, span is i+1 else difference between current and top index
spans[i] = i + 1ifnot stack else i - stack[-1]
# Push current index
stack.append(i)
return spans
if __name__ == '__main__':
prices = [100, 80, 60, 70, 60, 75, 85]
ss = StockSpan()
result = ss.calculate_span(prices)
print(result)
while stack and prices[stack[-1]] <= prices[i]:
pop indices with prices less or equal to current price to find last higher price
spans[i] = i + 1 if not stack else i - stack[-1]
calculate span as distance from last higher price or full length if none
stack.append(i)
push current day index for future comparisons
OutputSuccess
[1, 1, 1, 2, 1, 4, 6]
Complexity Analysis
Time: O(n) because each element is pushed and popped at most once
Space: O(n) for the stack and spans array storing results
vs Alternative: Naive approach is O(n^2) by checking all previous days for each day, stack reduces it to O(n)
Edge Cases
empty prices list
returns empty spans list without error
DSA Python
n = len(prices)
all prices equal
spans increase by 1 each day because all previous prices are <= current
DSA Python
while stack and prices[stack[-1]] <= prices[i]:
strictly decreasing prices
all spans are 1 because no previous price is less or equal
DSA Python
spans[i] = i + 1ifnot stack else i - stack[-1]
When to Use This Pattern
When you need to find the length of the span of consecutive elements up to current that satisfy a condition relative to current (like <= current value), and want to avoid repeated scanning, use a stack to remember boundaries for O(n) solution.
Common Mistakes
Mistake: Not popping all smaller or equal prices from stack, causing wrong span calculation Fix: Use a while loop to pop all indices with prices less or equal to current price before calculating span
Summary
Calculates, for each day, the number of consecutive days up to and including today with stock prices less or equal to current day's price using a stack.
Use when you want to find spans or ranges efficiently without checking all previous elements repeatedly.
The key insight is to use a stack to jump back to the last day with a higher price, skipping smaller or equal prices.