Stock Span Problem Using Stack in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a stack of integers for storing indices.

DSA C++

std::stack<[1]> s;

Drag options to blanks, or click blank then click option'

Afloat

Bdouble

Cchar

Dint

Attempts:

3 left

💡 Hint

Common Mistakes

Using float or double instead of int for indices.

Using char which is not suitable for indices.

We use a stack of integers to store indices of stock prices.

2fill in blank

medium

Complete the condition to pop from stack while current price is greater than or equal to price at stack top.

DSA C++

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

Drag options to blanks, or click blank then click option'

A>=

B<

C==

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using < instead of >= causes wrong logic.

Using == or <= does not correctly identify smaller or equal prices.

We pop while current price is greater than or equal to price at top index in stack.

3fill in blank

hard

Fix the error in calculating span when stack is empty.

DSA C++

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

Drag options to blanks, or click blank then click option'

Ai + 1

B-1

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 causes span to be zero incorrectly.

Using i alone misses the +1 count.

If stack is empty, span is i + 1 since it includes all days from the beginning up to the current day.

4fill in blank

hard

Fill both blanks to push current index and iterate over all prices.

DSA C++

for (int i = 0; i [1] n; i++) {
    // logic
    s.[2](i);
}

Drag options to blanks, or click blank then click option'

A<

B<=

Cpush

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= causes out of bounds error.

Using pop instead of push removes elements incorrectly.

We loop from 0 to n-1 using i < n and push current index i onto stack.

5fill in blank

hard

Fill all three blanks to complete the stock span function.

DSA C++

std::vector<int> calculateSpan(const std::vector<int>& price, int n) {
    std::stack<int> s;
    std::vector<int> span(n);
    span[0] = [1];
    s.push(0);
    for (int i = 1; i [2] n; i++) {
        while (!s.empty() && price[i] [3] price[s.top()]) {
            s.pop();
        }
        span[i] = s.empty() ? i + 1 : i - s.top();
        s.push(i);
    }
    return span;
}

Drag options to blanks, or click blank then click option'

A1

B<

C>=

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing span[0] to 0 causes wrong span.

Using i <= n causes index out of range.

Using < instead of >= in while condition breaks logic.

Initialize span[0] = 1, loop i < n, and pop while price[i] >= price at stack top.

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