Stock Span Problem Using Stack in DSA C# - Deep Dive

Overview - Stock Span Problem Using Stack

What is it?

The Stock Span Problem is about finding how many consecutive days before today the stock price was less than or equal to today's price. We use a stack to efficiently track these days. This helps us quickly calculate the span for each day without checking all previous days one by one.

Why it matters

Without this method, calculating stock spans would be slow and inefficient, especially for large data sets. Using a stack speeds up the process, saving time and computing power. This is important in real-world stock analysis where quick decisions matter.

Where it fits

Before learning this, you should understand basic arrays and stacks. After this, you can explore other stack-based problems like Next Greater Element or Histogram Area. This problem builds your skills in using stacks for efficient data processing.

Mental Model

Core Idea

Use a stack to remember previous days with higher stock prices so you can quickly find how far back the current price is greater or equal.

Think of it like...

Imagine a line of people waiting to buy tickets, where each person checks how many people in front have a lower or equal height. The stack helps keep track of taller people so you don't have to look at everyone every time.

Day:    1   2   3   4   5   6   7
Price:  100 80  60  70  60  75  85
Stack:  [1] [1] [1] [4] [4] [6] [7]
Span:   1   1   1   2   1   4   6

Stack stores indices of days with prices higher than current day.

Build-Up - 7 Steps

1

Foundation

Understanding Stock Span Problem

Concept: Introduce the problem of finding how many consecutive previous days have stock prices less or equal to today.

Given a list of daily stock prices, for each day, count how many days before it had prices less than or equal to the current day's price. For example, if prices are [100, 80, 60, 70, 60, 75, 85], the spans are [1, 1, 1, 2, 1, 4, 6].

Result

You understand the problem and expected output for a sample input.

Understanding the problem clearly is essential before learning how to solve it efficiently.

2

Foundation

Basic Stack Operations Refresher

Concept: Review how a stack works: push, pop, and peek operations.

A stack is like a pile of plates: you add (push) plates on top and remove (pop) from the top. Peek lets you see the top plate without removing it. This Last-In-First-Out behavior helps track recent items.

Result

You can use a stack to store and retrieve elements in reverse order of insertion.

Knowing stack basics is crucial because the solution depends on efficiently managing previous days' prices.

3

Intermediate

Naive Approach and Its Limitations

🤔Before reading on: do you think checking all previous days for each day is efficient or slow? Commit to your answer.

Concept: Explain the simple but slow method of checking all previous days for each price.

For each day, look back at all previous days until you find a day with a higher price. Count how many days had prices less or equal. This takes O(n^2) time for n days because each day may check many previous days.

Result

You see that the naive method works but is slow for large inputs.

Recognizing inefficiency motivates the need for a better approach using stacks.

4

Intermediate

Stack-Based Efficient Solution

🤔Before reading on: do you think a stack can help avoid checking all previous days? Commit to yes or no.

Concept: Use a stack to keep indices of days with prices higher than the current day to skip unnecessary checks.

We process days left to right. For each day, pop from the stack while the price at the top index is less or equal to current price. The stack top after popping is the previous day with a higher price. Span is current day index minus that index. Push current day index onto stack.

Result

The algorithm runs in O(n) time because each day is pushed and popped at most once.

Using a stack to remember only relevant days avoids repeated comparisons and speeds up the solution.

5

Intermediate

Implementing Stock Span in C#

🤔Before reading on: predict the output spans for prices [100, 80, 60, 70, 60, 75, 85]. Commit to your answer.

Concept: Write complete C# code using stack to solve the problem.

using System; using System.Collections.Generic; class StockSpan { public static int[] CalculateSpan(int[] prices) { int n = prices.Length; int[] span = new int[n]; Stack stack = new Stack(); for (int i = 0; i < n; 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); } return span; } static void Main() { int[] prices = {100, 80, 60, 70, 60, 75, 85}; int[] spans = CalculateSpan(prices); Console.WriteLine(string.Join(" ", spans)); } }

Result

Output: 1 1 1 2 1 4 6

Seeing the full code helps connect the stack logic to actual implementation and output.

6

Advanced

Handling Large Inputs Efficiently

🤔Before reading on: do you think this stack method uses extra memory proportional to input size? Commit to yes or no.

Concept: Analyze time and space complexity and how stack size behaves with input patterns.

The algorithm runs in O(n) time because each element is pushed and popped once. Space is O(n) in worst case when prices are strictly decreasing, so stack holds all indices. For random data, stack size varies but never exceeds n.

Result

You understand the performance guarantees and memory use of the stack solution.

Knowing complexity helps predict performance and memory needs in real applications.

7

Expert

Extending to Online and Real-Time Data

🤔Before reading on: can this stack approach be adapted to handle streaming stock prices one by one? Commit to yes or no.

Concept: Discuss how to maintain the stack and spans as new prices arrive in real-time.

Because the stack only depends on previous days, you can update it as new prices come in without recomputing from scratch. Just process each new price with the same logic, pushing and popping as needed. This makes it suitable for online systems.

Result

You see that the stack method supports efficient real-time updates.

Understanding online adaptation shows the method's practical power beyond static arrays.

Under the Hood

The stack stores indices of days with strictly higher prices than the current day. When processing a new day, popping from the stack removes days with prices less or equal, ensuring the top of the stack always points to the nearest previous day with a higher price. This allows calculating the span by subtracting indices.

Why designed this way?

This design avoids repeated scanning of previous days by remembering only relevant days. Alternatives like brute force were too slow. The stack approach balances time and space efficiently, inspired by similar problems like Next Greater Element.

Input prices: 100 80 60 70 60 75 85

Stack operations:
Day 1 (100): stack empty -> push 0
Stack: [0]

Day 2 (80): top=0 price=100 > 80 -> push 1
Stack: [0,1]

Day 3 (60): top=1 price=80 > 60 -> push 2
Stack: [0,1,2]

Day 4 (70): pop 2 (60 <= 70), top=1 price=80 > 70 -> push 3
Stack: [0,1,3]

Day 5 (60): top=3 price=70 > 60 -> push 4
Stack: [0,1,3,4]

Day 6 (75): pop 4 (60 <= 75), pop 3 (70 <= 75), top=1 price=80 > 75 -> push 5
Stack: [0,1,5]

Day 7 (85): pop 5 (75 <= 85), pop 1 (80 <= 85), top=0 price=100 > 85 -> push 6
Stack: [0,6]

Myth Busters - 3 Common Misconceptions

Quick: Does the stack store prices or indices? Commit to your answer.

Common Belief: The stack stores the actual stock prices to compare with current price.

Reality: The stack stores indices of days, not prices. Prices are accessed via these indices.

Why it matters: Storing prices directly would lose position information needed to calculate spans.

Quick: Is the span always the count of all previous days with lower prices? Commit yes or no.

Common Belief: Span counts all previous days with lower prices, regardless of order.

Reality: Span counts only consecutive previous days with prices less or equal, stopping at the first higher price.

Why it matters: Misunderstanding span definition leads to incorrect calculations and wrong results.

Quick: Does the stack approach always use less memory than naive? Commit yes or no.

Common Belief: Stack approach always uses less memory than naive method.

Reality: In worst case (strictly decreasing prices), stack holds all indices, using O(n) memory.

Why it matters: Assuming low memory use always can cause surprises in large inputs with decreasing prices.

Expert Zone

1

The stack only stores indices of days with strictly higher prices, never equal or lower, ensuring correctness and minimal size.

2

When prices are equal, the span includes those days because the condition is less or equal, affecting how popping is done.

3

The algorithm's O(n) time depends on each element being pushed and popped once, a subtle but crucial property.

When NOT to use

If you need spans based on non-consecutive days or different comparison criteria, this method won't work. Alternatives include segment trees or binary indexed trees for range queries.

Production Patterns

Used in financial software for quick technical analysis, real-time trading systems, and as a teaching example for stack-based optimization in interviews.

Connections

Next Greater Element

Builds-on and shares the same stack pattern to find next higher values efficiently.

Understanding stock span helps grasp Next Greater Element, a fundamental stack problem used in many algorithms.

Monotonic Stack

Stock span uses a monotonic decreasing stack to maintain order of prices.

Recognizing monotonic stacks unlocks many problems involving range queries and nearest greater/smaller elements.

Queueing Theory

Both involve managing sequences and conditions over time, though queueing focuses on waiting lines and service order.

Seeing how stacks and queues manage order differently deepens understanding of data structure choice in real systems.

Common Pitfalls

#1 Pushing prices instead of indices onto the stack.

Wrong approach:

stack.Push(prices[i]); // wrong: stores price, not index

Correct approach:

stack.Push(i); // correct: stores index for span calculation

Root cause:

Confusing the need to track position with the value itself.

#2 Not popping all smaller or equal prices before pushing current day.

Wrong approach:

if (stack.Count == 0 || prices[stack.Peek()] > prices[i]) stack.Push(i);

Correct approach:

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

Root cause:

Missing the loop to remove all irrelevant days leads to incorrect spans.

#3 Calculating span as stack.Peek() - i instead of i - stack.Peek().

Wrong approach:

span[i] = stack.Peek() - i; // wrong calculation

Correct approach:

span[i] = i - stack.Peek(); // correct calculation

Root cause:

Mixing up indices order causes negative or wrong span values.

Key Takeaways

The Stock Span Problem measures how many consecutive previous days had prices less or equal to today.

Using a stack to store indices of days with higher prices lets us calculate spans efficiently in O(n) time.

Each price is pushed and popped at most once, ensuring fast processing even for large inputs.

The stack-based solution can be adapted for real-time streaming data, making it practical for live stock analysis.

Understanding this problem builds a foundation for many other stack-related algorithms and optimizations.

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