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

↓

If stack empty -> span = current day index + 1

↓

Else span = current day index - top index on stack

↓

Push current day index onto stack

↓

Move to next day

↓

Repeat until all days processed

↓

Return span array

The flow shows how for each day's price, we pop smaller or equal prices from stack to find the span, then push current day index.

Execution Sample

DSA C

prices = [100, 80, 60, 70, 60, 75, 85];
stack = empty;
for i in range(len(prices)) {
  while stack not empty and prices[stack.top] <= prices[i]:
    stack.pop();
  span[i] = stack empty ? i+1 : i - stack.top;
  stack.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 Array	Visual State
1	Start	-	-	[]	[]	Stack empty, no spans computed
2	Process day 0	0	100	[]	[1]	Stack empty, span = 0+1=1, push 0 -> stack=[0]
3	Process day 1	1	80	[0]	[1, ?]	Top price 100 > 80, span=1-0=1, push 1 -> stack=[0,1]
4	Process day 2	2	60	[0,1]	[1,1,?]	Top price 80 > 60, span=2-1=1, push 2 -> stack=[0,1,2]
5	Process day 3	3	70	[0,1,2]	[1,1,1,?]	Pop 2 (60 <=70), stack=[0,1]; top price 80 >70, span=3-1=2, push 3 -> stack=[0,1,3]
6	Process day 4	4	60	[0,1,3]	[1,1,1,2,?]	Top price 70 > 60, span=4-3=1, push 4 -> stack=[0,1,3,4]
7	Process day 5	5	75	[0,1,3,4]	[1,1,1,2,1,?]	Pop 4 (60 <=75), stack=[0,1,3]; pop 3 (70 <=75), stack=[0,1]; top price 80 >75, span=5-1=4, push 5 -> stack=[0,1,5]
8	Process day 6	6	85	[0,1,5]	[1,1,1,2,1,4,?]	Pop 5 (75 <=85), stack=[0,1]; pop 1 (80 <=85), stack=[0]; top price 100 >85, span=6-0=6, push 6 -> stack=[0,6]
9	End	-	-	[0,6]	[1,1,1,2,1,4,6]	All days processed, final span array computed

💡 All days processed, loop ends.

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

Key Moments - 3 Insights

Why do we pop from the stack while the top price is less than or equal to the current price?

Because those days have prices not greater than current, so their span is included in current day's span. This is shown in steps 5, 7, and 8 where popping happens before calculating span.

Why is the span for day 0 equal to 1 even though the stack is empty?

When stack is empty, it means no previous higher price exists, so span is current day index + 1. Step 2 shows this with span=1 for day 0.

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

Indices help calculate span by subtracting positions. Also, prices can be accessed via indices. This is clear in the span calculation in steps 3-8.

Visual Quiz - 3 Questions

Look at the execution table at step 5. What is the span calculated for day 3?

A 1

B 3

C 2

D 4

💡 Hint

Check the 'Span Array' column at step 5 in the execution table.

At which step does the stack first contain three indices?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Stack (indices)' column to see when it reaches length 3.

If the price on day 6 was 50 instead of 85, what would happen to the span at day 6?

A Span would be 1

B Span would be 7

C Span would be 2

D Span would be 6

💡 Hint

Consider that price 50 is less than previous prices, so no popping occurs, span = i - top index.

Concept Snapshot

Stock Span Problem Using Stack:
- Use a stack to store indices of days with higher prices.
- For each day, pop stack while top price <= current price.
- If stack empty, span = current day index + 1.
- Else span = current day index - top index on stack.
- Push current day index onto stack.
- Repeat for all days to get span array.

Full Transcript

The Stock Span Problem calculates how many consecutive days before the current day had prices less than or equal to the current day'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 indices whose prices are less than or equal to the current price. If the stack becomes empty, the span is the current day index plus one, meaning all previous days had lower prices. Otherwise, the span is the difference between the current day index and the top index on the stack. We then push the current day index onto the stack and continue. This process efficiently computes the span for each day in one pass. The execution table shows step-by-step how the stack and span array change, and the variable tracker records the stack and span after each day. Key moments clarify why popping happens and why indices are stored. The visual quiz tests understanding of these 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 number of consecutive days before the current day with a price less than or equal to the current day's price

C. The difference between the highest and lowest stock price

D. The total sum of stock prices up to the current day

Solution

1. Step 1: Understand the problem definition

   The Stock Span Problem finds how many consecutive previous days had stock prices less than or equal to the current day's price.

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

   For each day, it counts the number of consecutive days before it with prices not greater than the current day's price.

3. Final Answer:

   The number of consecutive days with price less or equal to current day -> Option B

4. Quick Check:

   Span counts consecutive smaller/equal prices [OK]

Hint: Span counts consecutive days with price ≤ current day price [OK]

Common Mistakes:

• Confusing span with maximum price
• Calculating total sum instead of span
• Counting days with price greater than current

2. Which of the following C code snippets correctly initializes an empty stack for solving the Stock Span Problem?

easy

A. int stack[100]; int top = -1;

B. int stack[] = {0}; int top = 0;

C. int *stack; top = NULL;

D. stack = new int[100]; top = -1;

Solution

1. Step 1: Identify correct stack initialization in C

   In C, stack is usually an array with an integer top initialized to -1 to indicate empty stack.

2. Step 2: Check each option

   int stack[100]; int top = -1; correctly declares an int array and sets top to -1. int stack[] = {0}; int top = 0; initializes top to 0 which is incorrect for empty stack. int *stack; top = NULL; uses pointer and NULL incorrectly. stack = new int[100]; top = -1; uses 'new' which is C++ syntax, not C.

3. Final Answer:

   int stack[100]; int top = -1; -> Option A

4. Quick Check:

   Array + top = -1 initializes empty stack in C [OK]

Hint: Use array and top = -1 for empty stack in C [OK]

Common Mistakes:

• Using C++ 'new' keyword in C code
• Setting top to 0 instead of -1
• Using uninitialized pointers for stack

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 0: price=100, no previous, span=1
   Day 1: price=80, previous 100 > 80, span=1
   Day 2: price=60, previous 80 > 60, span=1
   Day 3: price=70, previous 60 ≤ 70, span=1+1=2
   Day 4: price=60, previous 70 > 60, span=1
   Day 5: price=75, previous 60 ≤ 75, count 1 (day4), previous 70 ≤ 75, count 2 (day3), previous 60 ≤ 75, count 3 (day2), previous 80 > 75 stop, span=4
   Day 6: price=85, previous 75 ≤ 85, count 1 (day5), previous 60 ≤ 85, count 2 (day4), previous 70 ≤ 85, count 3 (day3), previous 60 ≤ 85, count 4 (day2), previous 80 ≤ 85, count 5 (day1), previous 100 > 85 stop, span=6

2. Step 2: Write final 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 counts consecutive smaller/equal prices [OK]

Hint: Count consecutive previous days with price ≤ current day [OK]

Common Mistakes:

• Counting all previous days instead of consecutive
• Ignoring equal prices in span
• Miscounting span for days with fluctuating prices

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

for (int i = 0; i < n; i++) {
  while (top != -1 && prices[stack[top]] <= prices[i]) {
    top--;
  }
  span[i] = (top == -1) ? (i + 1) : (i - stack[top]);
  stack[++top] = i;
}

medium

A. The condition 'top != -1' should be 'top == -1'

B. The stack push operation should be before calculating span

C. No error; code correctly calculates the stock span

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

Solution

1. Step 1: Analyze the while loop condition

   The while loop pops indices from stack while the price at those indices is less than or equal to current price, which is correct for span calculation.

2. Step 2: Check span calculation and stack push

   Span is set to i+1 if stack empty, else difference between current index and top of stack index. Then current index is pushed. This matches the standard algorithm.

3. Final Answer:

   No error; code correctly calculates the stock span -> Option C

4. Quick Check:

   Standard stack-based span algorithm used [OK]

Hint: Check while condition and span formula carefully [OK]

Common Mistakes:

• Changing <= to < breaks span logic
• Pushing before span calculation causes wrong results
• Incorrect stack empty condition

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

hard

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

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

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

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

Solution

1. Step 1: Understand change from ≤ to < in comparison

   Changing from less or equal to strictly less means while popping from stack, we pop only if previous price is strictly less than current price, not equal.

2. Step 2: Calculate span with strict less condition

   Day 0: 10, span=1
   Day 1: 4, previous 10 > 4, span=1
   Day 2: 5, previous 4 < 5, pop 4, span=2
   Day 3: 90, previous 5 < 90, pop 5; previous 10 < 90, pop 10; stack empty, span=4
   Day 4: 120, previous 90 < 120, pop 90; stack empty, span=5
   Day 5: 80, previous 120 > 80, span=1 (no pop)
   But since we pop only if strictly less, equal prices would not pop. Here no equal prices affect.

3. Final Answer:

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

4. Quick Check:

   Strict less changes popping condition, span updated accordingly [OK]

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

Common Mistakes:

• Not updating while condition correctly
• Miscounting span for last day
• Assuming equal prices pop stack