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 or equal prices until a higher price is found.

intermediate

What does each element in the stack represent in the Stock Span Problem?

Each element in the stack stores the index of a day with a stock price higher than the current day's price, helping to calculate the span.

intermediate

How is the span for a day calculated using the stack?

Span = current day index - index of last higher price day (top of stack) if stack not empty; otherwise, span = current day index + 1.

beginner

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.

What does the Stock Span Problem measure for each day?

A Number of days with price higher than current day

B Number of consecutive previous days with price less than or equal to current day

C Total sum of prices till current day

D Difference between current and previous day price

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

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

A Array

B Queue

C Linked List

D Stack

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

When calculating span, if the stack is empty, what is the span for the current day?

A Current day index + 1

B 1

C 0

D Current day index

If no previous higher price exists, span is all days till current day, which is current day index + 1.

What does popping elements from the stack represent in the Stock Span Problem?

A Removing days with prices less than or equal to current day

B Adding new days to the stack

C Calculating sum of prices

D Resetting the stack

Popping removes days with prices less or equal to current day to find the last higher price day.

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

A O(n^2)

B O(n log n)

C O(n)

D O(log n)

Each element is pushed and popped at most once, so the solution runs in linear time O(n).

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

Think about how the stack keeps track of previous higher prices.

Describe the steps to calculate the span for each day in the Stock Span Problem using a stack.

Focus on how you use the stack to 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 average stock price up to the current day

B. The maximum stock price in the entire list

C. The difference between today's price and the previous day's price

D. The number of consecutive days up to the current day with a price less than or equal to today's price

Solution

1. Step 1: Understand the problem definition

   The Stock Span Problem finds how many days up to the current day had prices less than or equal to today's price consecutively.

2. Step 2: Identify what the span represents

   The span is the count of consecutive days including today where the price was not higher than today's price.

3. Final Answer:

   The number of consecutive days up to the current day with a price less than or equal to today's price -> Option D

4. Quick Check:

   Span counts consecutive days with price ≤ today [OK]

Hint: Span counts days with price ≤ today, including today [OK]

Common Mistakes:

• Confusing span with maximum price
• Thinking span is difference of prices
• Assuming span is average price

2. Which C++ STL container is most suitable to implement the Stock Span Problem efficiently?

easy

A. std::stack

B. std::vector

C. std::queue

D. std::list

Solution

1. Step 1: Identify the data structure needed for last-in-first-out access

   The Stock Span Problem requires checking previous days' prices in reverse order, which suits a stack.

2. Step 2: Choose the container that supports push/pop from one end efficiently

   std::stack provides push and pop operations on the top element, perfect for this problem.

3. Final Answer:

   std::stack -> Option A

4. Quick Check:

   Stack supports LIFO needed for span calculation [OK]

Hint: Use stack for last-in-first-out access in span problem [OK]

Common Mistakes:

• Using queue which is FIFO, not suitable
• Using vector without stack logic
• Using list which is less efficient here

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 1: 100 -> span=1
   Day 2: 80 < 100 -> span=1
   Day 3: 60 < 80 -> span=1
   Day 4: 70 > 60 -> span=2 (includes day 3 and 4)
   Day 5: 60 < 70 -> span=1
   Day 6: 75 > 60, 70, 60 -> span=4 (days 3 to 6)
   Day 7: 85 > 75, 70, 60, 80 -> span=6 (days 2 to 7)

2. Step 2: Write the span array

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

3. Final Answer:

   [1, 1, 1, 2, 1, 4, 6] -> Option A

4. Quick Check:

   Span array matches calculated values [OK]

Hint: Compare current price with stack top to count span [OK]

Common Mistakes:

• Counting all previous days regardless of price
• Confusing span with cumulative sum
• Ignoring consecutive condition

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

std::stack<int> s;
int n = prices.size();
std::vector<int> span(n);
for (int i = 0; i < n; i++) {
  while (!s.empty() && prices[s.top()] < prices[i]) {
    s.pop();
  }
  span[i] = s.empty() ? i + 1 : i - s.top();
  s.push(i);
}

medium

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

B. The span calculation should be i - s.top() + 1 instead of i - s.top()

C. Stack should store prices, not indices

D. The loop should start from i = 1, not 0

Solution

1. Step 1: Analyze the span calculation formula

   The span for day i is the number of consecutive days including today with price less than or equal to today's price.

2. Step 2: Check the formula used in code

   The code uses span[i] = s.empty() ? i + 1 : i - s.top(); but this misses counting the current day properly.

3. Step 3: Correct formula

   The correct formula is span[i] = s.empty() ? i + 1 : i - s.top() + 1 to include the current day.

4. Final Answer:

   The span calculation should be i - s.top() + 1 instead of i - s.top() -> Option B

5. Quick Check:

   Adding +1 accounts for the current day in span [OK]

Hint: Add +1 to index difference for correct span [OK]

Common Mistakes:

• Forgetting to add 1 in span calculation
• Storing prices instead of indices in stack
• Starting loop incorrectly at 1

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

hard

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

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

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

D. [1, 1, 1, 3, 4, 1]

Solution

1. Step 1: Modify comparison to strictly less than

   Change while condition to pop from stack while prices[s.top()] < prices[i], excluding equal prices.

2. Step 2: Calculate spans with strict less than

   Day 1: 10 -> span=1
   Day 2: 4 < 10 -> span=1
   Day 3: 5 > 4 -> span=2
   Day 4: 90 > 5,4,10 -> span=4
   Day 5: 120 > 90 -> span=5
   Day 6: 80 < 120 -> span=1

3. Final Answer:

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

4. Quick Check:

   Strict less than changes span for day 3 and 6 [OK]

Hint: Use < instead of <= in stack pop condition [OK]

Common Mistakes:

• Not changing comparison operator correctly
• Miscounting spans for equal prices
• Assuming spans remain same as original problem