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

Concept Flow - Stock Span Problem Using Stack

Start with empty stack

↓

For each price in array

↓

While stack not empty and top price <= current price

↓

Pop stack top

↓

Calculate span: current index - top of stack index or current index + 1 if stack empty

↓

Push current index onto stack

↓

Move to next price

↓

Repeat until all prices processed

↓

Return span array

The flow shows how we use a stack to keep indexes of prices. For each price, we pop smaller or equal prices from stack, then calculate span using the top of stack or full range if stack is empty, then push current index.

Execution Sample

DSA C#

int[] prices = {100, 80, 60, 70, 60, 75, 85};
int[] span = new int[prices.Length];
Stack<int> stack = new Stack<int>();

for (int i = 0; i < prices.Length; i++) {
  while (stack.Count > 0 && prices[stack.Peek()] <= prices[i]) stack.Pop();
  span[i] = stack.Count == 0 ? i + 1 : i - stack.Peek();
  stack.Push(i);
}

Calculates the stock span for each day using a stack to track indexes of previous higher prices.

Execution Table

Step	Operation	Current Price (Index)	Stack Content (Indexes)	Span Calculated	Visual State (Prices with Spans)
1	Start	-	[]	-	Prices: [100, 80, 60, 70, 60, 75, 85] Span: [-, -, -, -, -, -, -]
2	Process price 100 (0)	100 (0)	[]	0 + 1 = 1	Stack: [0] Span: [1, -, -, -, -, -, -]
3	Process price 80 (1)	80 (1)	[0]	1 - 0 = 1	Stack: [0,1] Span: [1,1, -, -, -, -, -]
4	Process price 60 (2)	60 (2)	[0,1]	2 - 1 = 1	Stack: [0,1,2] Span: [1,1,1, -, -, -, -]
5	Process price 70 (3)	70 (3)	[0,1,2]	Pop 2 (60 <= 70) Span = 3 - 1 = 2	Stack: [0,1,3] Span: [1,1,1,2, -, -, -]
6	Process price 60 (4)	60 (4)	[0,1,3]	4 - 3 = 1	Stack: [0,1,3,4] Span: [1,1,1,2,1, -, -]
7	Process price 75 (5)	75 (5)	[0,1,3,4]	Pop 4 (60 <= 75) Pop 3 (70 <= 75) Span = 5 - 1 = 4	Stack: [0,1,5] Span: [1,1,1,2,1,4, -]
8	Process price 85 (6)	85 (6)	[0,1,5]	Pop 5 (75 <= 85) Pop 1 (80 <= 85) Span = 6 - 0 = 6	Stack: [0,6] Span: [1,1,1,2,1,4,6]
9	End	-	[0,6]	-	Final Span: [1,1,1,2,1,4,6]

💡 All prices processed, stack contains indexes of prices with no greater price to the right.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
i	-	0	1	2	3	4	5	6	End
stack (indexes)	[]	[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,6]	[1,1,1,2,1,4,6]

Key Moments - 3 Insights

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

Because those prices are not useful for future span calculations; the current price covers their span. See execution_table steps 5, 7, and 8 where popping happens before calculating span.

What does it mean when the stack is empty before calculating span?

It means no previous price is higher than the current price, so the span is the entire range from day 0 to current day (i + 1). This happens at step 2 and is reflected in span calculation.

Why do we store indexes in the stack instead of prices?

Indexes help calculate the span by subtracting positions. Prices alone don't give position info. See variable_tracker stack content and span calculation in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the stack content after processing price 70?

A [0,3]

B [0,1,3]

C [0,1,2,3]

D [3]

💡 Hint

Check the 'Stack Content (Indexes)' column at step 5 in execution_table.

At which step does the span for price 75 become 4?

A Step 6

B Step 8

C Step 7

D Step 5

💡 Hint

Look at the 'Span Calculated' column in execution_table for price 75.

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

A Stack would pop more elements, possibly leaving only [0]

B Stack would remain the same as [0,1,2]

C Stack would be empty

D Stack would only contain [3]

💡 Hint

Consider the popping condition: prices[stack.Peek()] <= current price.

Concept Snapshot

Stock Span Problem Using Stack:
- Use a stack to store indexes of days with higher prices.
- For each price, pop stack while top price <= current price.
- Span = current index - top of stack index (or current index + 1 if stack empty).
- Push current index onto stack.
- Result: array of spans showing how many consecutive days price was less or equal.

Full Transcript

The Stock Span Problem calculates how many consecutive days up to and including the current day had prices less than or equal to the current price. We use a stack to keep indexes of days with higher prices. For each price, we pop from the stack all indexes with prices less than or equal to the current price. If the stack is empty, the span is the current index plus one, meaning all previous days had prices less than or equal to the current price. Otherwise, the span is the difference between the current index and the top index on the stack. We then push the current index onto the stack. This process repeats for all prices, resulting in the span array. The execution table shows step-by-step how the stack changes and how spans are calculated. Key moments clarify why we pop from the stack and why indexes are stored. The visual quiz tests understanding of stack content and span calculation at specific steps.

Practice

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 difference between the current day's price and the previous day's price

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 total sum of all stock prices up to the current day

Solution

1. Step 1: Understand the problem definition

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

2. Step 2: Clarify what is calculated for each day

   For each day, it counts consecutive previous days with prices not higher than the current day.

3. 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

4. Quick Check:

   Stock span = consecutive days with price ≤ current day price [OK]

Hint: Span counts consecutive previous days with price ≤ today [OK]

Common Mistakes:

• Confusing span with maximum price
• Counting all previous days instead of consecutive
• Calculating price differences instead of counts

2. Which of the following C# code snippets correctly declares a stack to be used for the Stock Span Problem?

easy

A. Stack<int> stack = new Stack<int>();

B. List<int> stack = new List<int>();

C. int[] stack = new int[10];

D. Queue<int> stack = new Queue<int>();

Solution

1. Step 1: Identify the correct data structure for stack

   In C#, Stack<T> is the built-in class for stack operations.

2. Step 2: Check each option's data structure

   Stack<int> stack = new Stack<int>(); uses Stack<int>, which is correct. int[] stack = new int[10]; uses array, List<int> stack = new List<int>(); uses List, which are not stacks. Queue<int> stack = new Queue<int>(); uses Queue, which is FIFO, not LIFO.

3. Final Answer:

   Stack<int> stack = new Stack<int>(); -> Option A

4. Quick Check:

   Stack<T> is the correct stack type in C# [OK]

Hint: Use Stack<int> for stack, not List or Queue [OK]

Common Mistakes:

• Using List instead of Stack
• Using Queue which is FIFO, not stack
• Using fixed-size array without stack methods

3. What is the output of the following C# code snippet for stock prices [100, 80, 60, 70, 60, 75, 85]?

int[] prices = {100, 80, 60, 70, 60, 75, 85};
int[] span = new int[prices.Length];
Stack<int> stack = new Stack<int>();

for (int i = 0; i < prices.Length; i++) {
    while (stack.Count > 0 && prices[stack.Peek()] <= prices[i]) {
        stack.Pop();
    }
    span[i] = (stack.Count == 0) ? (i + 1) : (i - stack.Peek());
    stack.Push(i);
}
Console.WriteLine(string.Join(", ", span));

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

1. Step 1: Trace the stack and span calculation for each price

   Day 0: stack empty, span[0] = 1, push 0
   Day 1: prices[0]=100 > 80, no pop, span[1] = 1 - 0 = 1, push 1
   Day 2: prices[1]=80 > 60, no pop, span[2] = 2 - 1 = 1, push 2
   Day 3: prices[2]=60 <= 70, pop 2; prices[1]=80 > 70, span[3] = 3 - 1 = 2, push 3
   Day 4: prices[3]=70 > 60, no pop, span[4] = 4 - 3 = 1, push 4
   Day 5: prices[4]=60 <= 75 pop 4; prices[3]=70 <= 75 pop 3; prices[1]=80 > 75 no pop, span[5] = 5 - 1 = 4, push 5
   Day 6: prices[5]=75 <= 85 pop 5; prices[1]=80 <= 85 pop 1; prices[0]=100 > 85 no pop, span[6] = 6 - 0 = 6, push 6

2. Step 2: Collect the span array

   The span array is [1, 1, 1, 2, 1, 4, 6].

3. Final Answer:

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

4. Quick Check:

   Span matches consecutive days with price ≤ current day [OK]

Hint: Pop smaller prices, span = current index - top stack index [OK]

Common Mistakes:

• Not popping all smaller or equal prices
• Using wrong index difference for span
• Confusing span with price values

4. Identify the error in the following C# code snippet for the Stock Span Problem:

int[] prices = {10, 4, 5, 90, 120, 80};
int[] span = new int[prices.Length];
Stack<int> stack = new Stack<int>();

for (int i = 0; i < prices.Length; i++) {
    while (stack.Count > 0 && prices[stack.Peek()] <= prices[i]) {
        stack.Pop();
    }
    span[i] = (stack.Count == 0) ? i : (i - stack.Peek());
    stack.Push(i);
}
Console.WriteLine(string.Join(", ", span));

medium

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

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

C. Stack should store prices, not indices

D. The span calculation should use i + 1 when stack is empty

Solution

1. Step 1: Check the span calculation when stack is empty

   When stack is empty, span should be i + 1 because all previous days are counted.

2. Step 2: Identify the error in span assignment

   Code uses span[i] = i instead of i + 1, which undercounts span for first element and others when stack is empty.

3. Final Answer:

   The span calculation should use i + 1 when stack is empty -> Option D

4. Quick Check:

   Empty stack span = i + 1, not i [OK]

Hint: Use i+1 for span if stack empty, not i [OK]

Common Mistakes:

• Using i instead of i+1 for empty stack span
• Storing prices in stack instead of indices
• Wrong comparison operator causing incorrect pops

5. Given a list of daily stock prices, how would you modify the Stock Span Problem algorithm to find the span of days where the price was strictly less than the current day's price (not less than or equal)?

hard

A. Calculate span by counting all previous days regardless of price

B. Change the comparison in the while loop from prices[stack.Peek()] <= prices[i] to prices[stack.Peek()] < prices[i]

C. Use a queue instead of a stack to track indices

D. Change the comparison in the while loop from prices[stack.Peek()] <= prices[i] to prices[stack.Peek()] >= prices[i]

Solution

1. Step 1: Understand the original comparison

   The original algorithm pops indices while prices at stack top are less than or equal to current price.

2. Step 2: Modify comparison for strictly less

   To count only days with price strictly less, change <= to < in the while condition.

3. Final Answer:

   Change the comparison in the while loop from prices[stack.Peek()] <= prices[i] to prices[stack.Peek()] < prices[i] -> Option B

4. Quick Check:

   Use < instead of ≤ for strict less span [OK]

Hint: Use < instead of <= in while condition for strict less [OK]

Common Mistakes:

• Using >= instead of < causing wrong pops
• Switching to queue which breaks logic
• Ignoring price comparison and counting all days