Stock Span Problem Using Stack in DSA C#

Mental Model

We want to find how many consecutive days before today had stock prices less or equal to today's price. We use a stack to remember days with higher prices to quickly find the span.

Analogy: Imagine a line of people with different heights. For each person, we want to count how many people before them are shorter or equal in height until we find a taller person. The stack helps us remember the taller people to skip over shorter ones quickly.

Prices: 100 80 60 70 60 75 85
Stack stores indices of days with prices higher than current day
Example stack after some steps:
[0]100 -> [1]80 -> [5]75 -> [6]85 -> null
↑ top of stack

Dry Run Walkthrough

Input: prices: [100, 80, 60, 70, 60, 75, 85]

Goal: Calculate the stock span array where each element shows how many consecutive days before had price less or equal to current day

Step 1: Process day 0 with price 100, stack empty so span is 1, push day 0

Stack: [0]100 -> null
Span: [1]

Why: No previous days, so span is 1

Step 2: Process day 1 with price 80, top stack price 100 > 80, span is 1, push day 1

Stack: [0]100 -> [1]80 -> null
Span: [1, 1]

Why: Previous day price higher, so span resets to 1

Step 3: Process day 2 with price 60, top stack price 80 > 60, span is 1, push day 2

Stack: [0]100 -> [1]80 -> [2]60 -> null
Span: [1, 1, 1]

Why: Previous day price higher, span is 1

Step 4: Process day 3 with price 70, pop day 2 (60 ≤ 70), top now day 1 (80 > 70), span = 3 - 1 = 2, push day 3

Stack: [0]100 -> [1]80 -> [3]70 -> null
Span: [1, 1, 1, 2]

Why: Pop smaller prices to find last higher price day, span is distance

Step 5: Process day 4 with price 60, top stack price 70 > 60, span is 1, push day 4

Stack: [0]100 -> [1]80 -> [3]70 -> [4]60 -> null
Span: [1, 1, 1, 2, 1]

Why: Previous day price higher, span resets

Step 6: Process day 5 with price 75, pop day 4 (60 ≤ 75), pop day 3 (70 ≤ 75), top now day 1 (80 > 75), span = 5 - 1 = 4, push day 5

Stack: [0]100 -> [1]80 -> [5]75 -> null
Span: [1, 1, 1, 2, 1, 4]

Why: Pop smaller prices to find last higher price day, span is distance

Step 7: Process day 6 with price 85, pop day 5 (75 ≤ 85), pop day 1 (80 ≤ 85), top now day 0 (100 > 85), span = 6 - 0 = 6, push day 6

Stack: [0]100 -> [6]85 -> null
Span: [1, 1, 1, 2, 1, 4, 6]

Why: Pop smaller prices to find last higher price day, span is distance

Result:

Span array: [1, 1, 1, 2, 1, 4, 6]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class StockSpan {
    public static int[] CalculateSpan(int[] prices) {
        int n = prices.Length;
        int[] span = new int[n];
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < n; i++) {
            // Pop indices with prices less or equal to current price
            while (stack.Count > 0 && prices[stack.Peek()] <= prices[i]) {
                stack.Pop();
            }

            // If stack empty, span is i+1 else difference
            span[i] = (stack.Count == 0) ? (i + 1) : (i - stack.Peek());

            // Push current day index
            stack.Push(i);
        }
        return span;
    }

    static void Main() {
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        int[] result = CalculateSpan(prices);
        Console.WriteLine(string.Join(", ", result));
    }
}

while (stack.Count > 0 && prices[stack.Peek()] <= prices[i]) { stack.Pop(); }

Pop indices of days with prices less or equal to current day to find last higher price day

span[i] = (stack.Count == 0) ? (i + 1) : (i - stack.Peek());

Calculate span as distance from last higher price day or full length if none

stack.Push(i);

Push current day index to stack for future comparisons

Output

1, 1, 1, 2, 1, 4, 6

Complexity Analysis

Time: O(n) because each price is pushed and popped at most once from the stack

Space: O(n) for the stack and span array to store indices and results

vs Alternative: Naive approach is O(n^2) by checking all previous days for each price, stack reduces it to O(n)

Edge Cases

Empty prices array

Returns empty span array without error

DSA C#

int n = prices.Length;

All prices equal

Span increases by 1 each day since all previous prices are less or equal

DSA C#

while (stack.Count > 0 && prices[stack.Peek()] <= prices[i]) { stack.Pop(); }

Strictly decreasing prices

Span is always 1 because no previous price is less or equal

DSA C#

span[i] = (stack.Count == 0) ? (i + 1) : (i - stack.Peek());

When to Use This Pattern

When you need to find how many previous elements satisfy a condition relative to current element efficiently, use a stack to keep track of indices of elements that break the condition.

Common Mistakes

Mistake: Not popping all smaller or equal prices from stack, leading to incorrect span calculation
Fix: Use a while loop to pop all indices with prices less or equal to current price before calculating span

Mistake: Calculating span as i - top of stack without checking if stack is empty
Fix: Check if stack is empty; if yes, span is i+1, else difference

Summary

Calculates how many consecutive previous days had stock prices less or equal to current day using a stack.

Use when you want to find spans or ranges efficiently without checking all previous elements repeatedly.

The key is to use a stack to remember indices of days with higher prices to quickly find the last higher price day.

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