Stock Span Problem Using Stack in DSA C++ - Execution Trace

Concept Flow - Stock Span Problem Using Stack

Start with empty stack

↓

For each day's price

↓

While stack not empty and top price <= current price

↓

Pop from stack

↓

Calculate span: if stack empty -> i+1 else i - top index

↓

Push current day index onto stack

↓

Move to next day

↓

Repeat until all days processed

↓

Return span array

We process each day's price, popping smaller or equal prices from stack to find the span, then push current day index.

Execution Sample

DSA C++

vector<int> prices = {100, 80, 60, 70, 60, 75, 85};
vector<int> span(prices.size());
stack<int> st;
for(int i = 0; i < prices.size(); i++) {
  while(!st.empty() && prices[st.top()] <= prices[i]) {
    st.pop();
  }
  span[i] = st.empty() ? i + 1 : i - st.top();
  st.push(i);
}

Calculates stock span for each day using a stack to track indices of days with higher prices.

Execution Table

Step	Operation	Current Day (i)	Price	Stack (Indices)	Span Calculated	Visual State
1	Start	-	-	[]	-	Empty stack, no spans yet
2	Process day 0	0	100	[]	1	Stack empty, span = 0+1=1, push 0 -> [0]
3	Process day 1	1	80	[0]	1	Top price 100 > 80, span = 1-0=1, push 1 -> [0,1]
4	Process day 2	2	60	[0,1]	1	Top price 80 > 60, span = 2-1=1, push 2 -> [0,1,2]
5	Process day 3	3	70	[0,1,2]	2	Pop 2 (60 <= 70), top now 1(80 > 70), span=3-1=2, push 3 -> [0,1,3]
6	Process day 4	4	60	[0,1,3]	1	Top price 70 > 60, span=4-3=1, push 4 -> [0,1,3,4]
7	Process day 5	5	75	[0,1,3,4]	4	Pop 4(60), pop 3(70), top 1(80 > 75), span=5-1=4, push 5 -> [0,1,5]
8	Process day 6	6	85	[0,1,5]	5	Pop 5(75), pop 1(80), top 0(100 > 85), span=6-0=6, push 6 -> [0,6]
9	End	-	-	[0,6]	-	All days processed, spans computed

💡 All days processed, stack contains indices of days with prices higher than last processed day

Variable Tracker

Variable	Start	After Day 0	After Day 1	After Day 2	After Day 3	After Day 4	After Day 5	After Day 6	Final
stack	[]	[0]	[0,1]	[0,1,2]	[0,1,3]	[0,1,3,4]	[0,1,5]	[0,6]	[0,6]
span	[]	[1]	[1,1]	[1,1,1]	[1,1,1,2]	[1,1,1,2,1]	[1,1,1,2,1,4]	[1,1,1,2,1,4,5]	[1,1,1,2,1,4,5]
i	-	0	1	2	3	4	5	6	-

Key Moments - 3 Insights

Why do we pop elements from the stack when the current price is higher or equal?

Because those days have prices less or equal to current, so their span ends before current day. See execution_table rows 5,7,8 where popping happens before calculating span.

Why do we calculate span as i+1 if stack is empty?

If stack is empty, no previous higher price exists, so span is all days from start to current (i+1). See execution_table row 2 where stack empty leads to span=1.

What does the stack store and why indices instead of prices?

Stack stores indices to calculate span as difference of indices. Prices alone can't give span length. See variable_tracker 'stack' row showing indices stored.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the stack after processing day 5?

A [0,1,3,4]

B [0,1,3]

C [0,1,5]

D [0,1,5,6]

💡 Hint

Check the 'Stack (Indices)' column at step 7 in execution_table

At which step does the span for a day become 2?

A Step 4

B Step 5

C Step 6

D Step 3

💡 Hint

Look at 'Span Calculated' column in execution_table for value 2

If the price on day 3 was 90 instead of 70, how would the stack change at step 5?

A Pop more elements, stack smaller

B No pop, stack grows larger

C Stack remains same as original

D Stack becomes empty

💡 Hint

Higher price causes popping of smaller or equal prices, see popping logic in execution_table steps 5 and 7

Concept Snapshot

Stock Span Problem Using Stack:
- Use stack to store indices of days with higher prices
- For each day, pop stack while top price <= current price
- Span = current index - top of stack if stack not empty, else current index + 1
- Push current day index onto stack
- Efficient O(n) solution for span calculation

Full Transcript

The Stock Span Problem calculates how many consecutive days before the current day had prices less or equal to today's price. We use a stack to keep track of indices of days with higher prices. For each day, we pop from the stack all days with prices less or equal to current price. If stack is empty after popping, span is current day index plus one, else span is difference between current day and top of stack. Then we push current day index onto stack. This process repeats for all days, resulting in an efficient O(n) solution. The stack helps quickly find the last day with a higher price, enabling span calculation without checking all previous days.

Practice

1. What does the Stock Span Problem calculate for each day in a list of stock prices?

easy

A. The average stock price up to the current day

B. The maximum stock price in the entire list

C. The difference between today's price and the previous day's price

D. The number of consecutive days up to the current day with a price less than or equal to today's price

Solution

1. Step 1: Understand the problem definition

   The Stock Span Problem finds how many days up to the current day had prices less than or equal to today's price consecutively.

2. Step 2: Identify what the span represents

   The span is the count of consecutive days including today where the price was not higher than today's price.

3. Final Answer:

   The number of consecutive days up to the current day with a price less than or equal to today's price -> Option D

4. Quick Check:

   Span counts consecutive days with price ≤ today [OK]

Hint: Span counts days with price ≤ today, including today [OK]

Common Mistakes:

• Confusing span with maximum price
• Thinking span is difference of prices
• Assuming span is average price

2. Which C++ STL container is most suitable to implement the Stock Span Problem efficiently?

easy

A. std::stack

B. std::vector

C. std::queue

D. std::list

Solution

1. Step 1: Identify the data structure needed for last-in-first-out access

   The Stock Span Problem requires checking previous days' prices in reverse order, which suits a stack.

2. Step 2: Choose the container that supports push/pop from one end efficiently

   std::stack provides push and pop operations on the top element, perfect for this problem.

3. Final Answer:

   std::stack -> Option A

4. Quick Check:

   Stack supports LIFO needed for span calculation [OK]

Hint: Use stack for last-in-first-out access in span problem [OK]

Common Mistakes:

• Using queue which is FIFO, not suitable
• Using vector without stack logic
• Using list which is less efficient here

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, 1, 2, 1, 4, 6]

B. [1, 2, 3, 4, 5, 6, 7]

C. [1, 1, 2, 2, 3, 3, 4]

D. [1, 1, 1, 1, 1, 1, 1]

Solution

1. Step 1: Calculate span for each day

   Day 1: 100 -> span=1
   Day 2: 80 < 100 -> span=1
   Day 3: 60 < 80 -> span=1
   Day 4: 70 > 60 -> span=2 (includes day 3 and 4)
   Day 5: 60 < 70 -> span=1
   Day 6: 75 > 60, 70, 60 -> span=4 (days 3 to 6)
   Day 7: 85 > 75, 70, 60, 80 -> span=6 (days 2 to 7)

2. Step 2: Write the span array

   The spans are [1, 1, 1, 2, 1, 4, 6].

3. Final Answer:

   [1, 1, 1, 2, 1, 4, 6] -> Option A

4. Quick Check:

   Span array matches calculated values [OK]

Hint: Compare current price with stack top to count span [OK]

Common Mistakes:

• Counting all previous days regardless of price
• Confusing span with cumulative sum
• Ignoring consecutive condition

4. Identify the error in this C++ code snippet for Stock Span calculation:

std::stack<int> s;
int n = prices.size();
std::vector<int> span(n);
for (int i = 0; i < n; i++) {
  while (!s.empty() && prices[s.top()] < prices[i]) {
    s.pop();
  }
  span[i] = s.empty() ? i + 1 : i - s.top();
  s.push(i);
}

medium

A. The comparison operator in while loop should be <= instead of <

B. The span calculation should be i - s.top() + 1 instead of i - s.top()

C. Stack should store prices, not indices

D. The loop should start from i = 1, not 0

Solution

1. Step 1: Analyze the span calculation formula

   The span for day i is the number of consecutive days including today with price less than or equal to today's price.

2. Step 2: Check the formula used in code

   The code uses span[i] = s.empty() ? i + 1 : i - s.top(); but this misses counting the current day properly.

3. Step 3: Correct formula

   The correct formula is span[i] = s.empty() ? i + 1 : i - s.top() + 1 to include the current day.

4. Final Answer:

   The span calculation should be i - s.top() + 1 instead of i - s.top() -> Option B

5. Quick Check:

   Adding +1 accounts for the current day in span [OK]

Hint: Add +1 to index difference for correct span [OK]

Common Mistakes:

• Forgetting to add 1 in span calculation
• Storing prices instead of indices in stack
• Starting loop incorrectly at 1

5. Given stock prices [10, 4, 5, 90, 120, 80], how would the Stock Span algorithm change if we want to find the span of days with prices strictly less than today's price (not less than or equal)? What is the resulting span array?

hard

A. [1, 1, 1, 4, 5, 1]

B. [1, 1, 2, 4, 5, 2]

C. [1, 1, 2, 4, 5, 1]

D. [1, 1, 1, 3, 4, 1]

Solution

1. Step 1: Modify comparison to strictly less than

   Change while condition to pop from stack while prices[s.top()] < prices[i], excluding equal prices.

2. Step 2: Calculate spans with strict less than

   Day 1: 10 -> span=1
   Day 2: 4 < 10 -> span=1
   Day 3: 5 > 4 -> span=2
   Day 4: 90 > 5,4,10 -> span=4
   Day 5: 120 > 90 -> span=5
   Day 6: 80 < 120 -> span=1

3. Final Answer:

   [1, 1, 2, 4, 5, 1] -> Option C

4. Quick Check:

   Strict less than changes span for day 3 and 6 [OK]

Hint: Use < instead of <= in stack pop condition [OK]

Common Mistakes:

• Not changing comparison operator correctly
• Miscounting spans for equal prices
• Assuming spans remain same as original problem