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 find the span.
Analogy: Imagine a line of people with different heights. For each person, we want to count how many people before them are shorter or equal in height until we find a taller person. The stack helps us remember the taller people to stop counting.
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 -> null
ā top of stack
Dry Run Walkthrough
Input: prices: [100, 80, 60, 70, 60, 75, 85]
Goal: Calculate the stock span for each day, which is the count of consecutive days before the current day with price less or equal to 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 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 stack 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 index 2 (60 ā¤ 70), top now index 1 (80 > 70), span = 3 - 1 = 2, push index 3
Stack: [0 -> 1 -> 3]
Span: [1, 1, 1, 2]
Why: Count days with price ā¤ 70 until a higher price found
Step 5: Process day 4 with price 60, top stack price 70 > 60, span is 1, push index 4
Stack: [0 -> 1 -> 3 -> 4]
Span: [1, 1, 1, 2, 1]
Why: Previous day price higher, span resets to 1
Step 6: Process day 5 with price 75, pop index 4 (60 ā¤ 75), pop index 3 (70 ā¤ 75), top now index 1 (80 > 75), span = 5 - 1 = 4, push index 5
Stack: [0 -> 1 -> 5]
Span: [1, 1, 1, 2, 1, 4]
Why: Count consecutive days with price ā¤ 75
Step 7: Process day 6 with price 85, pop index 5 (75 ā¤ 85), pop index 1 (80 ā¤ 85), top now index 0 (100 > 85), span = 6 - 0 = 6, push index 6
Stack: [0 -> 6]
Span: [1, 1, 1, 2, 1, 4, 6]
Why: Count consecutive days with price ā¤ 85
Result:
Span array: [1, 1, 1, 2, 1, 4, 6]
Annotated Code
DSA Typescript
class Stack {
private items: number[] = [];
push(element: number) {
this.items.push(element);
}
pop(): number | undefined {
return this.items.pop();
}
top(): number | undefined {
return this.items.length === 0 ? undefined : this.items[this.items.length - 1];
}
isEmpty(): boolean {
return this.items.length === 0;
}
}
function calculateSpan(prices: number[]): number[] {
const n = prices.length;
const span: number[] = new Array(n).fill(1);
const stack = new Stack();
for (let i = 0; i < n; i++) {
// Pop indices with prices less or equal to current price
while (!stack.isEmpty() && prices[stack.top()!] <= prices[i]) {
stack.pop();
}
// If stack empty, span is i+1else difference between current and top index
span[i] = stack.isEmpty() ? i + 1 : i - stack.top()!;
stack.push(i);
}
return span;
}
// Driver code
const prices = [100, 80, 60, 70, 60, 75, 85];
const result = calculateSpan(prices);
console.log(result.join(", "));
while (!stack.isEmpty() && prices[stack.top()!] <= prices[i]) { stack.pop(); }
Remove indices of days with prices less or equal to current day to find last higher price day
span[i] = stack.isEmpty() ? i + 1 : i - stack.top()!;
Calculate span based on distance to last higher price day or all previous if none
stack.push(i);
Add current day index to stack for future comparisons
OutputSuccess
1, 1, 1, 2, 1, 4, 6
Complexity Analysis
Time: O(n) because each price index is pushed and popped at most once
Space: O(n) for the stack and span array to store indices and 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 array
Returns empty span array without error
DSA Typescript
const n = prices.length;
All prices equal
Span increases by 1 each day because all previous prices are less or equal
DSA Typescript
while (!stack.isEmpty() && prices[stack.top()!] <= prices[i]) { stack.pop(); }
Strictly decreasing prices
Span is always 1 because no previous price is less or equal
DSA Typescript
span[i] = stack.isEmpty() ? i + 1 : i - stack.top()!;
When to Use This Pattern
When you need to find how many previous consecutive elements satisfy a condition relative to current, use a stack to track indices of elements that break the condition for efficient lookups.
Common Mistakes
Mistake: Not popping all smaller or equal prices from stack, leading to incorrect span calculation Fix: Use a while loop to pop all indices with prices less or equal to current price before calculating span
Mistake: Calculating span as i - top without checking if stack is empty, causing errors Fix: Check if stack is empty; if yes, span is i+1, else i - top index
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 of consecutive elements satisfying a condition efficiently.
The stack keeps indices of days with higher prices to quickly find the last day breaking the condition.
Practice
(1/5)
1. What does the Stock Span Problem calculate for each day in a list of stock prices?
easy
A. The average stock price over all days
B. The maximum stock price in the entire list
C. The number of consecutive days before the current day with a price less than or equal to the current day's price
D. The difference between the highest and lowest stock price
Solution
Step 1: Understand the problem definition
The Stock Span Problem finds how many days in a row before today had prices less than or equal to today's price.
Step 2: Identify what is calculated for each day
For each day, it counts consecutive previous days with prices not higher than current day.
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 C
Quick Check:
Stock span = consecutive days with price ā¤ current day price [OK]
Hint: Span counts days with price ā¤ today's price backward [OK]
Common Mistakes:
Thinking it finds max price overall
Confusing span with price difference
Calculating average price instead
2. Which TypeScript data structure is best suited to efficiently solve the Stock Span Problem?
easy
A. Stack
B. Array
C. Queue
D. Set
Solution
Step 1: Recall the problem needs to track previous prices efficiently
We need to quickly find previous days with prices less or equal to current day.
Step 2: Identify the data structure that supports last-in-first-out access
A stack allows pushing and popping previous prices to compare efficiently.
Final Answer:
Stack -> Option A
Quick Check:
Stack is used for last-in-first-out access [OK]
Hint: Use stack to track previous prices for quick comparison [OK]
Common Mistakes:
Using queue which is FIFO, not suitable
Using set which does not maintain order
Using array without stack logic
3. What is the output of the stock span array for prices [100, 80, 60, 70, 60, 75, 85]?
medium
A. [1, 1, 1, 2, 1, 3, 4]
B. [1, 1, 1, 1, 1, 1, 1]
C. [1, 2, 3, 4, 5, 6, 7]
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 (days 2 and 3) Day 4: 60 ā¤ 70 -> span 1 Day 5: 75 > 60, 70 -> span 4 (days 2,3,4,5) Day 6: 85 > 75, 70, 80 -> span 6 (days 1 to 6)
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: Count consecutive previous days with price ā¤ current day [OK]
Common Mistakes:
Counting all previous days regardless of price
Confusing span with cumulative sum
Miscounting days when price increases
4. Identify the error in this TypeScript snippet for Stock Span calculation:
function calculateSpan(prices: number[]): number[] {
const stack: number[] = [];
const span: number[] = [];
for (let i = 0; i < prices.length; i++) {
while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
stack.pop();
}
span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
stack.push(i);
}
return span;
}
medium
A. The stack should store prices, not indices
B. The comparison operator should be <= instead of < in while condition
C. The span array is not initialized with zeros
D. The loop should start from i = 1, not 0
Solution
Step 1: Analyze the while loop condition
The condition uses < to pop smaller prices, but equal prices should also be popped to count span correctly.
Step 2: Correct the comparison operator
Change < to <= so that prices equal to current price are popped, ensuring correct span calculation.
Final Answer:
The comparison operator should be <= instead of < in while condition -> Option B
Quick Check:
Use <= to include equal prices in span [OK]
Hint: Use <= in while to pop equal or smaller prices [OK]
Common Mistakes:
Using < misses equal prices in span
Storing prices instead of indices in stack
Starting loop from 1 misses first day
5. Given stock prices [10, 4, 5, 90, 120, 80], how would you modify the standard Stock Span algorithm to also return the day index of the last higher price before each day? What is the output for the last higher price indices array?
hard
A. [-1, 0, 0, -1, -1, 4]
B. [-1, 0, 1, -1, -1, 4]
C. [-1, 0, 0, 2, 3, 3]
D. [-1, -1, 1, 0, 1, 2]
Solution
Step 1: Modify algorithm to track last higher price index
Along with span, store index from stack top before popping. If stack empty, store -1.
Step 2: Calculate last higher price indices for each day
Day 0 (10): no previous higher -> -1 Day 1 (4): previous higher 10 at index 0 -> 0 Day 2 (5): previous higher 10 at index 0 -> 0 Day 3 (90): no previous higher -> -1 Day 4 (120): no previous higher -> -1 Day 5 (80): previous higher 120 at index 4 -> 4
Final Answer:
[-1, 0, 0, -1, -1, 4] -> Option A
Quick Check:
Last higher price indices match calculated values [OK]
Hint: Store stack top index before popping for last higher price [OK]
Common Mistakes:
Returning span instead of last higher price indices
Using price values instead of indices
Assigning wrong indices when stack is empty
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.
