We want to find how many consecutive days before today had stock prices less or equal to today's price. We use a stack to remember days with higher prices to quickly jump back.
Analogy: Imagine checking how many days in a row your friend scored less or equal points than you in a game. Instead of checking every day, you keep a list of days where your friend scored more, so you can skip many days at once.
Prices: [100, 80, 60, 70, 60, 75, 85]
Stack stores indices of days with prices higher than current day.
Example stack after some steps:
Index: 0 -> 1 -> 3 -> null
Prices:100 80 70
↑top
Dry Run Walkthrough
Input: prices: [100, 80, 60, 70, 60, 75, 85]
Goal: Calculate span for each day: how many consecutive days before had price ≤ current day's price
Step 1: Process day 0 with price 100, stack empty so span is 1, push index 0
Stack: [0]
Span: [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]
Span: [1, 1]
Why: Previous day price higher, so span resets to 1
Step 3: Process day 2 with price 60, top price 80 > 60, span is 1, push index 2
Stack: [0 -> 1 -> 2]
Span: [1, 1, 1]
Why: Previous day price higher, span is 1
Step 4: Process day 3 with price 70, pop indices while top price ≤ 70: pop 2 (60 ≤ 70), top now 1 (80 > 70), span = 3 - 1 = 2, push 3
Stack: [0 -> 1 -> 3]
Span: [1, 1, 1, 2]
Why: Count days since last higher price day
Step 5: Process day 4 with price 60, top price 70 > 60, span is 1, push 4
Stack: [0 -> 1 -> 3 -> 4]
Span: [1, 1, 1, 2, 1]
Why: Previous day price higher, span resets
Step 6: Process day 5 with price 75, pop while top price ≤ 75: pop 4 (60 ≤ 75), pop 3 (70 ≤ 75), top now 1 (80 > 75), span = 5 - 1 = 4, push 5
Stack: [0 -> 1 -> 5]
Span: [1, 1, 1, 2, 1, 4]
Why: Count days since last higher price day
Step 7: Process day 6 with price 85, pop while top price ≤ 85: pop 5 (75 ≤ 85), pop 1 (80 ≤ 85), top now 0 (100 > 85), span = 6 - 0 = 6, push 6
Stack: [0 -> 6]
Span: [1, 1, 1, 2, 1, 4, 6]
Why: Count days since last higher price day
Result:
Span array: [1, 1, 1, 2, 1, 4, 6]
Annotated Code
DSA Go
package main
import (
"fmt"
)
type Stack []int
func (s *Stack) Push(v int) {
*s = append(*s, v)
}
func (s *Stack) Pop() int {
v := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return v
}
func (s *Stack) Top() int {
return (*s)[len(*s)-1]
}
func (s *Stack) IsEmpty() bool {
returnlen(*s) == 0
}
func calculateSpan(prices []int) []int {
span := make([]int, len(prices))
var stack Stack
for i := 0; i < len(prices); i++ {
// Pop indices while current price >= price at stack top
for !stack.IsEmpty() && prices[stack.Top()] <= prices[i] {
stack.Pop() // remove days with price less or equal
}
if stack.IsEmpty() {
span[i] = i + 1 // no higher price before
} else {
span[i] = i - stack.Top() // distance from last higher price
}
stack.Push(i) // push current day index
}
return span
}
func main() {
prices := []int{100, 80, 60, 70, 60, 75, 85}
span := calculateSpan(prices)
for i, s := range span {
fmt.Printf("Day %d (Price %d): Span %d\n", i, prices[i], s)
}
}
for i := 0; i < len(prices); i++ {
iterate over each day to calculate span
for !stack.IsEmpty() && prices[stack.Top()] <= prices[i] {
pop days with price less or equal to current day price
stack.Pop() // remove days with price less or equal
remove indices of days that can't limit current span
if stack.IsEmpty() {
if no higher price before, span is current day index + 1
span[i] = i + 1 // no higher price before
span covers all days from start to current
span[i] = i - stack.Top() // distance from last higher price
span is days since last higher price day
stack.Push(i) // push current day index
add current day to stack for future comparisons
OutputSuccess
Day 0 (Price 100): Span 1
Day 1 (Price 80): Span 1
Day 2 (Price 60): Span 1
Day 3 (Price 70): Span 2
Day 4 (Price 60): Span 1
Day 5 (Price 75): Span 4
Day 6 (Price 85): Span 6
Complexity Analysis
Time: O(n) because each price is pushed and popped at most once
Space: O(n) for the stack and span array storing results
vs Alternative: Naive approach checks all previous days for each price leading to O(n^2), stack reduces it to O(n)
Edge Cases
empty prices array
returns empty span array without error
DSA Go
for i := 0; i < len(prices); i++ {
all prices equal
span increases by 1 each day since all previous prices are ≤ current
DSA Go
for !stack.IsEmpty() && prices[stack.Top()] <= prices[i] {
strictly decreasing prices
span is always 1 because no previous price is ≤ current
DSA Go
if stack.IsEmpty() {
When to Use This Pattern
When asked to find how many previous elements satisfy a condition relative to current, use a stack to jump back efficiently instead of checking all previous elements.
Common Mistakes
Mistake: Not popping all smaller or equal prices from stack, causing incorrect span calculation Fix: Use a while loop to pop all indices with prices ≤ current price before calculating span
Mistake: Calculating span as i - top index + 1 instead of i - top index Fix: Span is distance between current index and last higher price index, so use i - stack.Top()
Summary
Calculates how many consecutive previous days had stock prices less or equal to current day using a stack.
Use when you need to find spans or ranges efficiently without checking all previous elements repeatedly.
The key insight is to keep indices of days with strictly higher prices on a stack to quickly find the last higher price day.
Practice
(1/5)
1. What does the stock span problem calculate for each day in a list of stock prices?
easy
A. The number of consecutive days before the current day with a price less than or equal to the current day's price
B. The maximum stock price in the entire list
C. The difference between the highest and lowest stock price
D. The total sum of stock prices up to the current day
Solution
Step 1: Understand the problem definition
The stock span for a day is the count of consecutive previous days with prices less than or equal to that day's price.
Step 2: Clarify what is being calculated
It is not about maximum price or sums, but about consecutive days with lower or equal prices.
Final Answer:
The number of consecutive days before the current day with a price less than or equal to the current day's price -> Option A
Quick Check:
Stock span = consecutive days with price ≤ current price [OK]
Hint: Span counts consecutive days with price ≤ current day price [OK]
Common Mistakes:
Confusing span with maximum price
Thinking span is total sum of prices
Ignoring consecutive days condition
2. Which Go data structure is best suited to efficiently solve the stock span problem?
easy
A. Stack
B. Array
C. Queue
D. Map
Solution
Step 1: Identify the data structure for tracking previous prices
The stack helps keep track of indices of days with prices to compare efficiently.
Step 2: Understand why stack is efficient
Stack allows popping smaller prices and quickly finding the last higher price day, enabling O(n) time complexity.
Final Answer:
Stack -> Option A
Quick Check:
Stack is used for efficient previous price tracking [OK]
Hint: Use stack to track previous days' prices efficiently [OK]
Common Mistakes:
Using array leads to O(n²) time
Queue does not support backward checks
Map is not suitable for order-based checks
3. What is the output span array for the stock prices [100, 80, 60, 70, 60, 75, 85] using the stock span algorithm?
medium
A. [1, 1, 2, 2, 3, 3, 4]
B. [1, 2, 3, 4, 5, 6, 7]
C. [1, 1, 1, 1, 1, 1, 1]
D. [1, 1, 1, 2, 1, 4, 6]
Solution
Step 1: Calculate span for each day
Day 0: 100 -> span=1 (no previous) Day 1: 80 ≤ 100 -> span=1 Day 2: 60 ≤ 80 -> span=1 Day 3: 70 > 60 -> span=2 (includes day 2) Day 4: 60 ≤ 70 -> span=1 Day 5: 75 > 60, 70 -> span=4 (includes days 4,3,2) Day 6: 85 > 75, 70, 60, 80 -> span=6 (includes days 5,4,3,2,1)
Step 2: Confirm final span array
The spans are [1, 1, 1, 2, 1, 4, 6].
Final Answer:
[1, 1, 1, 2, 1, 4, 6] -> Option D
Quick Check:
Span array matches calculated values [OK]
Hint: Pop smaller prices from stack to count span [OK]
Common Mistakes:
Counting all previous days instead of consecutive
Not popping smaller prices from stack
Confusing span with price values
4. Identify the bug in this Go code snippet for stock span calculation:
func calculateSpan(prices []int) []int {
n := len(prices)
span := make([]int, n)
stack := []int{}
for i := 0; i < n; i++ {
for len(stack) > 0 && prices[stack[len(stack)-1]] <= prices[i] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
span[i] = i + 1
} else {
span[i] = i - stack[len(stack)-1]
}
stack = append(stack, i)
}
return span
}
medium
A. The loop should start from i = 1 instead of 0
B. The comparison operator should be <= instead of < in the inner loop
C. Span array is not initialized with correct size
D. Stack should store prices, not indices
Solution
Step 1: Analyze the inner loop condition
The inner loop pops indices while the price at stack top is less than current price. It should pop while less than or equal to handle equal prices correctly.
Step 2: Understand impact of using < instead of <=
Using < misses popping equal prices, causing incorrect span counts for equal prices.
Final Answer:
The comparison operator should be <= instead of < in the inner loop -> Option B
Quick Check:
Use <= to correctly handle equal prices [OK]
Hint: Use <= in comparison to handle equal prices correctly [OK]
Common Mistakes:
Stack storing prices instead of indices
Incorrect span array size
Starting loop from wrong index
5. Given stock prices [10, 4, 5, 90, 120, 80], how would you modify the stock span algorithm to also return the day index of the last higher price before the current day? What is the output for the last higher price indices array?
hard
A. [ -1, 0, 1, -1, -1, 4 ]
B. [ -1, 0, 0, 2, 3, 3 ]
C. [-1, 0, 0, -1, -1, 4]
D. [ 0, -1, 1, 2, 3, 4 ]
Solution
Step 1: Modify algorithm to track last higher price index
Use stack to store indices; for each day, pop while current price ≥ price at stack top. If stack empty, last higher index is -1; else top of stack is last higher index.
Step 2: Calculate last higher price indices for given prices
Prices: [10,4,5,90,120,80] Day 0: empty -> -1 Day 1: 10 > 4, no pop -> 0 Day 2: 4 <= 5 pop 1, 10 > 5 -> 0 Day 3: 5 <= 90 pop 2, 10 <= 90 pop 0, empty -> -1 Day 4: 90 <= 120 pop 3, empty -> -1 Day 5: 120 > 80, no pop -> 4
Final Answer:
[-1, 0, 0, -1, -1, 4] -> Option C
Quick Check:
Last higher indices track previous greater price day [OK]
Hint: Track last higher price index using stack top or -1 if empty [OK]
Common Mistakes:
Returning span instead of last higher index
Not handling empty stack case (-1)
Confusing last higher index with span count
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.
