Stock Span Problem Using Stack in DSA C++

Mental Model

We find how many consecutive days before today had stock prices less or equal to today's price by using a stack to remember previous days.

Analogy: Imagine a line of people with different heights. For each person, you look back to count how many people before them are shorter or equal in height until you find a taller person.

Prices: 100 80 60 70 60 75 85
Stack stores indices of days with prices in decreasing order:
[0]100 -> [1]80 -> [3]70 -> [5]75 -> [6]85 -> null
Current day ↑

Dry Run Walkthrough

Input: prices: [100, 80, 60, 70, 60, 75, 85]

Goal: Calculate the stock span for each day, which is how many consecutive days before including today have price less or equal to today's price.

Step 1: Start with day 0, price 100, stack empty, push day 0

Stack: [0]
Span: [1]

Why: First day always has span 1 because no previous days

Step 2: Day 1, price 80, top of stack day 0 price 100 > 80, push day 1

Stack: [0, 1]
Span: [1, 1]

Why: Price 80 is less than 100, so span is 1

Step 3: Day 2, price 60, top stack day 1 price 80 > 60, push day 2

Stack: [0, 1, 2]
Span: [1, 1, 1]

Why: Price 60 less than 80, span is 1

Step 4: Day 3, price 70, pop day 2 (60 ≤ 70), top now day 1 (80 > 70), push day 3

Stack: [0, 1, 3]
Span: [1, 1, 1, 2]

Why: Count days with price ≤ 70 before day 3: day 2 only, so span 2

Step 5: Day 4, price 60, top stack day 3 price 70 > 60, push day 4

Stack: [0, 1, 3, 4]
Span: [1, 1, 1, 2, 1]

Why: Price 60 less than 70, span 1

Step 6: Day 5, price 75, pop day 4 (60 ≤ 75), pop day 3 (70 ≤ 75), top day 1 (80 > 75), push day 5

Stack: [0, 1, 5]
Span: [1, 1, 1, 2, 1, 4]

Why: Count days with price ≤ 75 before day 5: days 4,3,2 (popped), span 4

Step 7: Day 6, price 85, pop day 5 (75 ≤ 85), pop day 1 (80 ≤ 85), top day 0 (100 > 85), push day 6

Stack: [0, 6]
Span: [1, 1, 1, 2, 1, 4, 6]

Why: Count days with price ≤ 85 before day 6: days 5,4,3,2,1 (popped), span 6

Result:

Span array: [1, 1, 1, 2, 1, 4, 6]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<int> calculateSpan(const vector<int>& prices) {
    int n = prices.size();
    vector<int> span(n);
    stack<int> s; // stores indices of days

    for (int i = 0; i < n; i++) {
        // Pop indices while current price is higher or equal
        while (!s.empty() && prices[s.top()] <= prices[i]) {
            s.pop();
        }
        // If stack empty, span is i+1 else difference
        span[i] = s.empty() ? (i + 1) : (i - s.top());
        s.push(i);
    }
    return span;
}

int main() {
    vector<int> prices = {100, 80, 60, 70, 60, 75, 85};
    vector<int> span = calculateSpan(prices);

    for (int val : span) {
        cout << val << " ";
    }
    cout << endl;
    return 0;
}

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

Pop indices of days with prices less or equal to current price to find last higher price day

span[i] = s.empty() ? (i + 1) : (i - s.top());

Calculate span as distance from last higher price day or full length if none

s.push(i);

Push current day index to stack for future comparisons

Output

1 1 1 2 1 4 6 

Complexity Analysis

Time: O(n) because each element is pushed and popped at most once from the stack

Space: O(n) for the stack and span array to store indices and results

vs Alternative: Naive approach is O(n^2) by checking all previous days for each day, stack reduces it to O(n)

Edge Cases

Empty price list

Returns empty span array without error

DSA C++

int n = prices.size(); vector<int> span(n);

All prices equal

Span increases by 1 each day because all previous prices are less or equal

DSA C++

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

Strictly decreasing prices

Span is always 1 because no previous price is less or equal

DSA C++

span[i] = s.empty() ? (i + 1) : (i - s.top());

When to Use This Pattern

When asked to find how many previous consecutive elements satisfy a condition relative to current, use a stack to track indices for efficient look-back.

Common Mistakes

Mistake: Not popping all smaller or equal prices from stack, causing incorrect span calculation
Fix: Use a while loop to pop all indices with prices less or equal to current price before calculating span

Summary

Calculates how many consecutive previous days have stock prices less or equal to current day using a stack.

Use when you need to find spans or ranges of previous elements meeting a condition efficiently.

The key is to use a stack to remember indices of days with strictly higher prices to quickly find the span.

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