Stock Span Problem Using Stack in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Stock Span Problem?

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

intermediate

Why do we use a stack to solve the Stock Span Problem?

A stack helps keep track of previous days' prices efficiently, allowing us to find the span for each day in O(n) time by popping smaller prices until a higher price is found.

intermediate

In the Stock Span Problem, what does each element in the stack represent?

Each element in the stack represents a pair of (day index, stock price) where the price is greater than the prices of days popped before it.

intermediate

What is the time complexity of the Stock Span Problem solution using a stack?

The time complexity is O(n) because each element is pushed and popped at most once.

beginner

What is the output of the Stock Span Problem for prices [100, 80, 60, 70, 60, 75, 85]?

The output spans are [1, 1, 1, 2, 1, 4, 6].

What does the span represent in the Stock Span Problem?

A Total number of days

B Number of days with price greater than current day

C Number of consecutive days before current day with price less or equal

D Difference between highest and lowest price

Span counts how many consecutive previous days had prices less than or equal to the current day's price.

Which data structure is best suited to solve the Stock Span Problem efficiently?

A Queue

B Stack

C Array

D Linked List

Stack allows efficient tracking of previous higher prices to calculate spans in O(n) time.

What is the time complexity of the stack-based Stock Span solution?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

Each price is pushed and popped at most once, resulting in O(n) time.

If the current day's price is lower than the price at the top of the stack, what do we do?

A Push current day onto stack

B Pop from stack

C Ignore current day

D Clear the stack

We push the current day because it cannot extend the span of previous days with higher prices.

For prices [10, 4, 5, 90, 120, 80], what is the span for price 90?

A 5

B 3

C 1

D 4

Span for 90 includes days with prices 5, 4, and 10 before it, so span is 4.

Explain how a stack helps solve the Stock Span Problem efficiently.

Think about how you find the last day with a higher price before today.

Describe the steps to calculate the span for each day given stock prices using a stack.

Focus on how you use the stack to find the previous 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