Why Stock Span Problem Using Stack in DSA C#?

The Big Idea

Discover how a simple stack can save you hours of tedious work in stock analysis!

The Scenario

Imagine you are tracking daily stock prices on paper. For each day, you want to know how many consecutive previous days had prices less than or equal to today's price.

Doing this by checking every previous day manually for each new day is like flipping back pages repeatedly in a thick notebook.

The Problem

Manually checking each previous day's price for every new day takes a lot of time and effort. It's slow and easy to make mistakes, especially when you have many days to track.

This approach grows slower as the number of days increases, making it frustrating and inefficient.

The Solution

The Stock Span Problem using a stack helps solve this by remembering only important days' prices. It quickly skips over days that don't matter, so you don't have to check every day again and again.

This makes the process fast and easy, even for many days.

Before vs After

✗ Before

for (int i = 0; i < n; i++) {
    int span = 1;
    for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; j--) {
        span++;
    }
    spans[i] = span;
}

✓ After

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

What It Enables

This method enables fast calculation of stock spans for large datasets, making real-time stock analysis practical and efficient.

Real Life Example

Stock traders use this to quickly understand how long a stock price has been rising, helping them decide when to buy or sell without wasting time on slow calculations.

Key Takeaways

Manual checking is slow and error-prone for many days.

Using a stack skips unnecessary checks, speeding up the process.

Efficient span calculation helps in fast stock market decisions.

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