We find, for each day, the number of consecutive days (including today) up to today with stock prices less than or equal to today's price by using a stack to remember indices of previous days with higher prices.
Analogy: Imagine a line of people with different heights. For each person, we want to count how many consecutive people before them (including themselves) are shorter or equal in height until we find a taller person.
Prices: 100 -> 80 -> 60 -> 70 -> 60 -> 75 -> 85 -> null
Stack stores indices of days with prices in decreasing order
Example stack: [0, 1, 5] means days 0, 1, 5 with prices 100, 80, 75
Dry Run Walkthrough
Input: prices: [100, 80, 60, 70, 60, 75, 85]
Goal: Calculate span for each day: number of consecutive days (including current day) with price less or equal to current day
Step 1: Start with day 0, price 100, stack empty, push day 0
Stack: [0]
Span: [1]
Why: First day always has span 1 because no previous days
Step 2: Day 1, price 80, top of stack day 0 price 100 > 80, push day 1
Stack: [0, 1]
Span: [1, 1]
Why: Price 80 is less than 100, so span is 1
Step 3: Day 2, price 60, top stack day 1 price 80 > 60, push day 2
Stack: [0, 1, 2]
Span: [1, 1, 1]
Why: Price 60 less than 80, span is 1
Step 4: Day 3, price 70, pop day 2 (60 ≤ 70), now top day 1 price 80 > 70, push day 3
Stack: [0, 1, 3]
Span: [1, 1, 1, 2]
Why: Days up to day 3 with price ≤ 70: days 2, 3; span = 3 - 1 = 2
Step 5: Day 4, price 60, top day 3 price 70 > 60, push day 4
Stack: [0, 1, 3, 4]
Span: [1, 1, 1, 2, 1]
Why: Price 60 less than 70, span is 1
Step 6: Day 5, price 75, pop day 4 (60 ≤ 75), pop day 3 (70 ≤ 75), top day 1 price 80 > 75, push day 5
Stack: [0, 1, 5]
Span: [1, 1, 1, 2, 1, 4]
Why: Days up to day 5 with price ≤ 75: days 2, 3, 4, 5; span = 5 - 1 = 4
Step 7: Day 6, price 85, pop day 5 (75 ≤ 85), pop day 1 (80 ≤ 85), top day 0 price 100 > 85, push day 6
Stack: [0, 6]
Span: [1, 1, 1, 2, 1, 4, 6]
Why: Days up to day 6 with price ≤ 85: days 1, 2, 3, 4, 5, 6; span = 6 - 0 = 6
Result:
Span array: [1, 1, 1, 2, 1, 4, 6]
Annotated Code
DSA Javascript
class StockSpan {
static calculateSpan(prices) {
const n = prices.length;
const span = new Array(n).fill(1);
const stack = [];
for (let i = 0; i < n; i++) {
// Pop indices with prices less or equal to current price
while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
stack.pop();
}
// If stack empty, span is i+1else difference between current and top stack index
span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
stack.push(i);
}
return span;
}
}
// Driver code
const prices = [100, 80, 60, 70, 60, 75, 85];
const spans = StockSpan.calculateSpan(prices);
console.log(spans.join(' '));
Span is always 1 because no previous price is less or equal
DSA Javascript
span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
When to Use This Pattern
When asked to find how many previous consecutive elements satisfy a condition relative to current, use a stack to track indices for efficient lookups.
Common Mistakes
Mistake: Not popping all previous indices with prices less or equal to current, causing incorrect span calculation Fix: Use a while loop to pop all such indices before calculating span
Mistake: Calculating span as i - stack top without checking if stack is empty, causing errors Fix: Check if stack is empty; if yes, span is i+1 else difference
Summary
Calculates, for each day, the number of consecutive days (including the current day) with stock prices less or equal to current day using a stack.
Use when you need to find spans or counts of consecutive elements meeting a condition efficiently.
The key is to keep a stack of indices with strictly decreasing prices to quickly find 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 minimum stock price in the entire list
D. The difference between the current day's price and the previous day's price
Solution
Step 1: Understand the problem definition
The Stock Span Problem finds how many consecutive days before today had prices less than or equal to today's price.
Step 2: Clarify what is calculated for each day
For each day, it counts days backward until a higher price is found or start is reached.
Final Answer:
The number of consecutive days with price less or equal to current day -> Option A
Quick Check:
Span counts consecutive lower/equal prices before today [OK]
Hint: Span counts days with prices ≤ current day price [OK]
Common Mistakes:
Confusing span with max or min price
Thinking span is price difference
Ignoring consecutive days condition
2. Which of the following JavaScript code snippets correctly initializes an empty stack for solving the Stock Span Problem?
easy
A. const stack = 0;
B. const stack = {};
C. const stack = [];
D. const stack = null;
Solution
Step 1: Identify the correct data structure for stack
In JavaScript, a stack is usually implemented as an array to use push and pop methods.
Step 2: Check initialization syntax
An empty array is initialized with [] which is correct for a stack.
Final Answer:
const stack = []; -> Option C
Quick Check:
Stack uses array [] in JavaScript [OK]
Hint: Use array [] to create stack in JavaScript [OK]
Common Mistakes:
Using object {} instead of array
Assigning null or number instead of array
Forgetting to initialize stack before use
3. What is the output of the stock span array for the prices [100, 80, 60, 70, 60, 75, 85] using the Stock Span Problem algorithm?
medium
A. [7, 6, 5, 4, 3, 2, 1]
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 price
Day 0: 100 -> span=1 (no previous days) 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, 60 -> span=4 (days 4,3,2,1) Day 6: 85 > 75, 70, 60, 80 -> span=6 (days 5,3,2,1,0)
Step 2: Write the 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 [OK]
Common Mistakes:
Counting all previous days instead of consecutive
Mixing up greater and less conditions
Incorrectly including days with higher prices
4. Identify the error in the following JavaScript code snippet for the Stock Span Problem:
function calculateSpan(prices) {
const stack = [];
const span = [];
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 span calculation formula is incorrect; it should be i + stack[stack.length - 1]
B. There is no error; the code correctly calculates the stock span
C. The stack should store prices, not indices
D. The comparison operator in while loop should be <= instead of <
Solution
Step 1: Analyze the while loop condition
The loop pops indices while the price at top index is less than or equal to current price, which is correct for span calculation.
Step 2: Check span calculation formula
If stack is empty, span is i+1 (all previous days), else difference between current index and top index in stack, which is correct.
Step 3: Verify stack usage
Stack stores indices, which is standard to access prices array correctly.
Final Answer:
There is no error; the code correctly calculates the stock span -> Option B
Quick Check:
Code matches standard stock span algorithm [OK]
Hint: Stack stores indices; span formula uses index difference [OK]
Common Mistakes:
Changing < to <= breaks correct span logic
Storing prices instead of indices causes wrong indexing
Incorrect span formula leads to wrong results
5. Given the stock prices array [10, 4, 5, 90, 120, 80], how would the Stock Span Problem algorithm change if we want to find the span of days with prices strictly less than the current day's price (not less than or equal)? What is the resulting span array?
hard
A. [1, 1, 2, 4, 5, 1]
B. [1, 1, 2, 3, 4, 1]
C. [1, 1, 1, 4, 5, 1]
D. [1, 2, 3, 4, 5, 6]
Solution
Step 1: Understand the strict less than condition
Change the comparison in the algorithm from ≤ to <, so only days with price strictly less count towards span.
Step 2: Calculate spans with strict less than
Day 0: 10 -> span=1 Day 1: 4 < 10 -> span=1 Day 2: 5 > 4 -> span=2 (days 1 and 2) Day 3: 90 > 5,4,10 -> span=4 (days 0,1,2,3) Day 4: 120 > 90 -> span=5 (days 0 to 4) Day 5: 80 < 120 -> span=1
Final Answer:
[1, 1, 2, 4, 5, 1] -> Option A
Quick Check:
Strict less than span matches [1,1,2,4,5,1] [OK]
Hint: Use < instead of ≤ in comparison for strict span [OK]
Common Mistakes:
Not changing comparison operator correctly
Counting equal prices in span incorrectly
Miscounting consecutive days with strict condition
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.
