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 is like flipping back pages in a notebook repeatedly.

The Problem

Manually checking each previous day for every new price is slow and tiring. It takes a lot of time as the number of days grows.

You might lose track or make mistakes counting how many days to look back.

The Solution

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

This makes finding the span for each day fast and easy.

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> days;
for (int i = 0; i < n; i++) {
  while (!days.empty() && prices[days.top()] <= prices[i]) {
    days.pop();
  }
  spans[i] = days.empty() ? (i + 1) : (i - days.top());
  days.push(i);
}

What It Enables

This method enables fast calculation of stock spans for large data sets, making real-time stock analysis possible.

Real Life Example

Stock traders use this to quickly understand how many days a stock price has been rising or stable, helping them decide when to buy or sell.

Key Takeaways

Manual checking is slow and error-prone.

Using a stack skips unnecessary checks efficiently.

Stock span calculation becomes fast and scalable.

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