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.
Practice
(1/5)
1. What does the Stock Span Problem calculate for each day in a list of stock prices?
easy
A. The maximum stock price in the entire list
B. The number of consecutive days before the current day with price less than or equal to current day's price
C. The difference between current day's price and previous day's price
D. The total sum of stock prices up to the current day
Solution
Step 1: Understand the problem goal
The Stock Span Problem finds how many days before today had prices less than or equal to today's price consecutively.
Step 2: Clarify what is counted
It counts consecutive days backward until a higher price is found or start is reached.
Final Answer:
The number of consecutive days before the current day with price less than or equal to current day's price -> Option B
Quick Check:
Span counts consecutive lower/equal prices [OK]
Hint: Span counts consecutive days with price ≤ today's price [OK]
Common Mistakes:
Thinking it counts all previous days regardless of price
Confusing span with price difference
Assuming it finds max price instead
2. Which of the following Python code snippets correctly initializes an empty stack for solving the Stock Span Problem?
easy
A. stack = None
B. stack = {}
C. stack = []
D. stack = ()
Solution
Step 1: Identify correct stack data structure
In Python, a stack is commonly implemented using a list, so an empty stack is an empty list: stack = []
Step 2: Check other options
{} is a dictionary, () is a tuple (immutable), None is no value, so they are incorrect for stack.
Final Answer:
stack = [] -> Option C
Quick Check:
Empty list is stack [OK]
Hint: Use empty list [] to start a stack in Python [OK]
Common Mistakes:
Using {} which is a dictionary, not stack
Using () which is immutable tuple
Assigning None instead of a list
3. What is the output of the following code snippet for prices = [100, 80, 60, 70, 60, 75, 85]?
def calculate_span(prices):
stack = []
span = [0]*len(prices)
for i in range(len(prices)):
while stack and prices[stack[-1]] <= prices[i]:
stack.pop()
span[i] = i + 1 if not stack else i - stack[-1]
stack.append(i)
return span
print(calculate_span(prices))
medium
A. [1, 1, 1, 2, 1, 4, 6]
B. [1, 2, 3, 4, 5, 6, 7]
C. [7, 6, 5, 4, 3, 2, 1]
D. [1, 1, 2, 2, 3, 3, 4]
Solution
Step 1: Trace the loop and stack operations
For each price, pop indices with prices ≤ current price, then calculate span as distance from last higher price index or i+1 if none.
Step 2: Calculate spans for each day
Day 0: stack empty, span=1; Day 1: price 80 ≤ 100? No pop, span=1; Day 2: 60 ≤ 80? No pop, span=1; Day 3: 70 > 60 pop index 2, span=2; Day 4: 60 ≤ 70 no pop, span=1; Day 5: 75 > 60 pop index 4, 75 > 70 pop index 3, span=4; Day 6: 85 > 75 pop index 5, 85 > 100 no pop, span=6.
Final Answer:
[1, 1, 1, 2, 1, 4, 6] -> Option A
Quick Check:
Span array matches expected output [OK]
Hint: Pop smaller prices, span = current index - last higher index [OK]
Common Mistakes:
Not popping all smaller or equal prices
Calculating span as i instead of difference
Confusing span with price values
4. Identify the error in this Stock Span code snippet:
def stock_span(prices):
stack = []
span = []
for i in range(len(prices)):
while stack and prices[stack[-1]] < prices[i]:
stack.pop()
if not stack:
span.append(i)
else:
span.append(i - stack[-1])
stack.append(i)
return span
print(stock_span([10, 4, 5, 90, 120, 80]))
medium
A. Stack is not initialized correctly
B. The function returns None instead of span list
C. Comparison operator should be <= instead of <
D. Span for first day should be 1, but code appends 0
Solution
Step 1: Check span calculation for first day
When stack is empty, span should be i+1 (1 for first day), but code appends i (0 for first day), causing wrong span.
Step 2: Confirm other parts are correct
Stack initialization and popping logic are fine; comparison operator < is acceptable; function returns span list correctly.
Final Answer:
Span for first day should be 1, but code appends 0 -> Option D
Quick Check:
Span for day 0 must be 1 [OK]
Hint: Span on empty stack = i+1, not i [OK]
Common Mistakes:
Appending i instead of i+1 when stack empty
Using wrong comparison operator causing wrong pops
Not initializing span list properly
5. Given a list of stock prices, how would you modify the Stock Span algorithm to handle the case where prices can be equal and you want the span to include days with strictly less price only (exclude equal prices)?
hard
A. Change the comparison in while loop to prices[stack[-1]] < prices[i]
B. Change the comparison in while loop to prices[stack[-1]] <= prices[i]
C. Add an extra condition to skip equal prices after popping
D. No change needed; current algorithm already excludes equal prices
Solution
Step 1: Understand current comparison
Current algorithm uses <= to pop indices with prices less than or equal to current price, including equal prices in span.
Step 2: Modify to exclude equal prices
To exclude equal prices, change comparison to strictly less than (<) so equal prices stop popping and are not included in span.
Final Answer:
Change the comparison in while loop to prices[stack[-1]] < prices[i] -> Option A
Quick Check:
Use < to exclude equal prices [OK]
Hint: Use < instead of <= to exclude equal prices in span [OK]
Common Mistakes:
Using <= keeps equal prices included
Adding extra conditions unnecessarily
Assuming no change is needed
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.
