Stock Span Problem Using Stack in DSA C++ - Build from Scratch

Stock Span Problem Using Stack

📖 Scenario: You are working as a stock analyst. You want to find out how many consecutive days before today the stock price was less than or equal to today's price. This helps in understanding the stock's performance trend.

🎯 Goal: Build a program that calculates the stock span for each day using a stack data structure.

📋 What You'll Learn

Create a vector called prices with the exact values: 100, 80, 60, 70, 60, 75, 85

Create an empty stack called st to store indices

Create a vector called span of the same size as prices to store span values

Use a for loop with variable i to iterate over prices

Calculate the stock span using the stack and store it in span[i]

Print the span vector values separated by spaces

💡 Why This Matters

🌍 Real World

Stock analysts use the stock span problem to understand how long a stock price has been rising or stable, which helps in making investment decisions.

💼 Career

Understanding stacks and their applications is important for software developers working on financial software, data analysis tools, and algorithm optimization.

1

Create the stock prices vector

Create a vector of integers called prices with these exact values: 100, 80, 60, 70, 60, 75, 85

DSA C++

#include 
#include 
#include 

int main() {

    // Create the prices vector
    // Your code here

    return 0;
}

Hint

Use std::vector<int> and initialize it with the given values inside curly braces.

2

Create the stack and span vector

Create an empty stack of integers called st and a vector of integers called span with the same size as prices initialized with zeros

DSA C++

#include 
#include 
#include 

int main() {
    std::vector prices = {100, 80, 60, 70, 60, 75, 85};

    // Create stack and span vector
    // Your code here

    return 0;
}

Hint

Use std::stack<int> for the stack and initialize span with the size of prices filled with zeros.

3

Calculate the stock span using the stack

Use a for loop with variable i from 0 to prices.size(). Inside the loop, pop from st while it is not empty and prices[st.top()] <= prices[i]. Then set span[i] to i + 1 if st is empty, else to i - st.top(). Finally, push i onto st

DSA C++

#include 
#include 
#include 

int main() {
    std::vector prices = {100, 80, 60, 70, 60, 75, 85};
    std::stack st;
    std::vector span(prices.size(), 0);

    // Calculate span using stack
    // Your code here

    return 0;
}

Hint

Use a for loop to iterate over prices. Use a while loop to pop smaller or equal prices from the stack. Calculate span based on whether the stack is empty or not, then push the current index.

4

Print the stock span values

Use a for loop with variable i from 0 to span.size() and print span[i] followed by a space. Then print a newline

DSA C++

#include 
#include 
#include 

int main() {
    std::vector prices = {100, 80, 60, 70, 60, 75, 85};
    std::stack st;
    std::vector span(prices.size(), 0);

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

    // Print the span values
    // Your code here

    return 0;
}

Hint

Use a for loop to print each value in span followed by a space. Then print a newline.

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