Stock Span Problem Using Stack in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Stock Span Calculation

What is the output of the following C++ code that calculates the stock span for given prices?

DSA C++

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> calculateSpan(const vector<int>& prices) {
    vector<int> span(prices.size());
    stack<int> s; // stores indices
    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() {
    vector<int> prices = {100, 80, 60, 70, 60, 75, 85};
    vector<int> result = calculateSpan(prices);
    for (int val : result) {
        cout << val << " ";
    }
    return 0;
}

A 1 1 1 2 1 4 6

B 1 1 1 1 1 1 1

C 1 2 3 1 2 1 1

D 7 6 5 4 3 2 1

💡 Hint

Think about how the stack helps find the previous higher price index.

The stock span for each day is the count of consecutive days before it with price less or equal. The stack stores indices of days with higher prices to calculate spans efficiently.

🧠 Conceptual

intermediate

Understanding Stack Usage in Stock Span

Why do we use a stack to solve the Stock Span Problem efficiently?

A To hold the maximum stock price seen so far only.

B To store all stock prices in sorted order for binary search.

C To keep track of indices of previous days with higher stock prices for quick span calculation.

D To reverse the order of stock prices for easier processing.

💡 Hint

Think about how the stack helps find the nearest greater element to the left.

The stack stores indices of days with prices greater than the current day's price, allowing quick calculation of how many consecutive days had lower or equal prices.

🔧 Debug

advanced

Identify the Bug in Stock Span Code

What error will the following code produce when calculating stock span?

DSA C++

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> calculateSpan(const vector<int>& prices) {
    vector<int> span(prices.size());
    stack<int> s;
    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() {
    vector<int> prices = {100, 80, 60, 70, 60, 75, 85};
    vector<int> result = calculateSpan(prices);
    for (int val : result) {
        cout << val << " ";
    }
    return 0;
}

A No error, runs correctly

B Compilation error: missing semicolon

C Logical error: incorrect span values

D Runtime error: out_of_range due to accessing prices[7]

💡 Hint

Check the loop boundary condition carefully.

The loop runs with i <= prices.size(), which causes access to prices[7] when prices size is 7, leading to out_of_range runtime error.

🚀 Application

advanced

Stock Span for Large Input

Given a large array of stock prices, which approach is best to calculate the stock span efficiently?

A Use nested loops to compare each price with all previous prices.

B Use a stack to track indices of previous higher prices and calculate spans in one pass.

C Sort the prices and then calculate spans based on sorted order.

D Use a queue to store prices and calculate spans by dequeuing.

💡 Hint

Consider time complexity for large inputs.

Using a stack allows O(n) time complexity by avoiding repeated comparisons, unlike nested loops which are O(n^2). Sorting changes order and is not suitable.

❓ Predict Output

expert

Output of Modified Stock Span Code with Equal Prices

What is the output of this modified stock span code where prices can be equal?

DSA C++

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> calculateSpan(const vector<int>& prices) {
    vector<int> span(prices.size());
    stack<int> s;
    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() {
    vector<int> prices = {100, 100, 60, 70, 70, 75, 85};
    vector<int> result = calculateSpan(prices);
    for (int val : result) {
        cout << val << " ";
    }
    return 0;
}

A 1 2 1 2 1 5 6

B 1 1 1 2 2 3 4

C 1 1 1 1 1 1 1

D 7 6 5 4 3 2 1

💡 Hint

Note the difference in comparison operator in while loop.

The code uses '<' instead of '<=' so equal prices are counted as part of the span, increasing span counts for equal consecutive prices.

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