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. It helps investors understand the trend of stock prices. We solve this efficiently using a stack, a special data structure that helps keep track of previous prices. This problem shows how stacks can speed up calculations that seem slow at first.

Why it matters

Without this problem's solution, checking stock trends would take a long time, especially for many days. Investors would struggle to quickly analyze price patterns, losing chances to make smart decisions. The stack-based method makes this fast and practical, showing how data structures solve real-world problems. It teaches how to handle sequences and comparisons efficiently.

Where it fits

Before this, learners should know basic arrays and how stacks work. After this, they can explore other stack problems like Next Greater Element or learn about queues and sliding window techniques. This problem is a stepping stone to mastering efficient data processing in sequences.

Mental Model

Core Idea

Use a stack to remember previous days with higher stock prices to quickly find how far back prices were lower or equal.

Think of it like...

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

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

Legend:
- Stack stores indices of days with prices higher than current day.
- Span is count of consecutive days with price <= current day.

Build-Up - 6 Steps

1

Foundation

Understanding Stock Span Problem

Concept: Learn what the stock span means and how to calculate it by comparing prices day by day.

The stock span for a day is the number of consecutive days before it (including today) where the stock price was less than or equal to today's price. For example, if prices are [100, 80, 60, 70, 60, 75, 85], the span for day 4 (price 70) is 2 because day 3's price (60) is less than 70, but day 2's price (80) is higher, so we stop there.

Result

You understand that span counts how many days back prices were not higher than today.

Knowing the problem definition clearly helps you see why a simple loop might be slow and why a better method is needed.

2

Foundation

Introduction to Stack Data Structure

Concept: Learn what a stack is and how it works with push and pop operations.

A stack is like a pile of plates: you add (push) plates on top and remove (pop) the top plate first. It follows Last-In-First-Out (LIFO) order. In programming, stacks help remember recent items and remove them when no longer needed.

Result

You can use a stack to keep track of previous days' prices efficiently.

Understanding stack operations is key to solving the stock span problem efficiently.

3

Intermediate

Naive Approach to Stock Span

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

Concept: Calculate span by checking each previous day until a higher price is found.

For each day, start from the previous day and move backward until you find a day with a higher price. Count how many days you moved back. This works but takes a lot of time if prices are increasing.

Result

For prices [100, 80, 60, 70, 60, 75, 85], the naive method calculates spans as [1,1,1,2,1,4,6].

This method is simple but slow (O(n^2)) for large data, showing the need for a better approach.

4

Intermediate

Stack-Based Efficient Solution

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

Concept: Use a stack to store indices of days with higher prices to jump over smaller prices quickly.

Initialize an empty stack. For each day: - While stack is not empty and price at stack top <= current price, pop stack. - If stack is empty, span = current day index + 1. - Else, span = current day index - stack top index. - Push current day index onto stack. This way, you only visit each day once.

Result

Span array for [100, 80, 60, 70, 60, 75, 85] is [1,1,1,2,1,4,6] computed in O(n) time.

Using a stack reduces repeated comparisons, making the solution efficient and scalable.

5

Advanced

Implementing Stock Span in C++

🤔Before reading on: Can you predict the output of the code for input prices [100, 80, 60, 70, 60, 75, 85]? Commit to your answer.

Concept: Write complete C++ code using stack to compute stock spans.

#include #include #include std::vector calculateSpan(const std::vector& prices) { std::stack s; // stores indices std::vector span(prices.size()); for (int i = 0; i < prices.size(); ++i) { while (!s.empty() && prices[s.top()] <= prices[i]) { s.pop(); } span[i] = s.empty() ? (i + 1) : (i - s.top()); s.push(i); } return span; } int main() { std::vector prices = {100, 80, 60, 70, 60, 75, 85}; std::vector spans = calculateSpan(prices); for (int s : spans) { std::cout << s << " "; } std::cout << std::endl; return 0; }

Result

Output: 1 1 1 2 1 4 6

Seeing the full code helps connect the theory to practice and confirms the stack logic works as expected.

6

Expert

Optimizations and Edge Cases

🤔Before reading on: Do you think the stack solution handles all edge cases like equal prices or empty input correctly? Commit to yes or no.

Concept: Explore how the stack solution handles equal prices, empty input, and large data efficiently.

The stack solution treats equal prices as less or equal, so they extend the span. For empty input, it returns an empty span array. The algorithm runs in O(n) time and O(n) space, optimal for this problem. It can be adapted for streaming data by processing prices as they come.

Result

The solution is robust and efficient for all valid inputs, including edge cases.

Understanding edge cases and performance ensures the solution is production-ready and reliable.

Under the Hood

The stack stores indices of days with prices higher than the current day. When a new price arrives, the algorithm pops all indices with prices less or equal to it, effectively skipping those days. This means each index is pushed and popped at most once, making the algorithm O(n). The span is calculated by the difference between current day and the last higher price day.

Why designed this way?

The problem needed a way to avoid checking all previous days repeatedly. Using a stack to remember only relevant days (those with higher prices) reduces unnecessary comparisons. This design balances time and space efficiently, unlike naive methods that check all days.

Prices: 100  80  60  70  60  75  85
Index:   0   1   2   3   4   5   6

Stack operations:
Day 0: push 0 [100]
Day 1: 80 <= 100, push 1 [100,80]
Day 2: 60 <= 80, push 2 [100,80,60]
Day 3: 70 > 60 pop 2, 70 <= 80 push 3 [100,80,70]
Day 4: 60 <= 70 push 4 [100,80,70,60]
Day 5: 75 > 60 pop 4, 75 > 70 pop 3, 75 <= 80 push 5 [100,80,75]
Day 6: 85 > 75 pop 5, 85 > 80 pop 1, 85 <= 100 push 6 [100,85]

Span calculation:
span[i] = i - top_of_stack_after_popping

Myth Busters - 4 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 easily.

Reality: The stack stores indices of days, not prices, to calculate spans using positions.

Why it matters: Storing prices instead of indices makes it impossible to calculate spans correctly and leads to wrong results.

Quick: Is the time complexity of the stack solution O(n^2)? Commit to yes or no.

Common Belief: Because of the while loop inside the for loop, the solution is O(n^2).

Reality: Each element is pushed and popped at most once, so the overall time complexity is O(n).

Why it matters: Misunderstanding complexity may lead to rejecting an efficient solution and using slower methods.

Quick: Does the span count only strictly lower prices or also equal prices? Commit to your answer.

Common Belief: Span counts only days with strictly lower prices than today.

Reality: Span counts days with prices less than or equal to today's price.

Why it matters: Incorrect span calculation leads to wrong analysis of stock trends.

Quick: Can the stack solution handle empty input without errors? Commit to yes or no.

Common Belief: The stack solution will fail or crash on empty input.

Reality: The solution returns an empty span array gracefully for empty input.

Why it matters: Assuming failure on empty input may cause unnecessary checks or crashes in real systems.

Expert Zone

1

The stack solution implicitly maintains a monotonic decreasing stack of prices, which is a powerful pattern for many sequence problems.

2

Handling equal prices by popping ensures spans include consecutive equal prices, which is subtle but important for correctness.

3

The algorithm can be adapted for online streaming data by maintaining the stack state between inputs.

When NOT to use

If you only need to find spans for a small number of days or one-off queries, a simple loop might suffice. For problems requiring maximum spans over sliding windows, other data structures like deque or segment trees are better.

Production Patterns

In real trading systems, this pattern is used to quickly analyze price trends and trigger alerts. It also appears in competitive programming as a classic stack problem to test understanding of monotonic stacks.

Connections

Monotonic Stack

The stock span problem is a classic example of using a monotonic stack to solve range queries efficiently.

Understanding this problem helps grasp the broader pattern of monotonic stacks used in many sequence and array problems.

Sliding Window Maximum

Both problems use data structures to efficiently find maximum or span over a range, but sliding window uses deque instead of stack.

Knowing the difference helps choose the right data structure for range-based queries.

Human Queue Behavior in Lines

The way the stack tracks previous higher prices is like how people in a queue notice taller people ahead and skip shorter ones.

This connection shows how algorithms mimic real-world patterns of attention and comparison.

Common Pitfalls

#1 Storing prices in the stack instead of indices.

Wrong approach:

std::stack s; // stores prices
for (int i = 0; i < prices.size(); ++i) {
while (!s.empty() && s.top() <= prices[i]) s.pop();
// Cannot calculate span correctly here
s.push(prices[i]);
}

Correct approach:

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

Root cause:

Confusing the need for position information (indices) with just price values.

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

Wrong approach:

for (int i = 0; i < prices.size(); ++i) {
if (!s.empty() && prices[s.top()] <= prices[i]) {
// Missing loop to pop all smaller or equal
s.pop();
}
int span = s.empty() ? (i + 1) : (i - s.top());
s.push(i);
}

Correct approach:

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

Root cause:

Not realizing multiple smaller or equal prices must be removed to find the correct span.

#3 Assuming span counts only strictly smaller prices.

Wrong approach:

while (!s.empty() && prices[s.top()] < prices[i]) { s.pop(); }

Correct approach:

while (!s.empty() && prices[s.top()] <= prices[i]) { s.pop(); }

Root cause:

Misunderstanding the problem definition about equal prices.

Key Takeaways

The stock span problem measures how many consecutive previous days had prices less than or equal to today's price.

Using a stack to store indices of days with higher prices allows efficient O(n) computation by skipping unnecessary comparisons.

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

Correctly handling equal prices and empty inputs is essential for a robust solution.

This problem is a classic example of monotonic stacks, a powerful pattern for many sequence problems.

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