Min Stack Design in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Min Stack Operations Sequence

What is the output printed by the following C++ code that uses a Min Stack?

DSA C++

#include <stack>
class MinStack {
private:
    std::stack<int> s, minS;
public:
    void push(int x) {
        s.push(x);
        if(minS.empty() || x <= minS.top()) {
            minS.push(x);
        }
    }
    void pop() {
        if(s.top() == minS.top()) {
            minS.pop();
        }
        s.pop();
    }
    int top() {
        return s.top();
    }
    int getMin() {
        return minS.top();
    }
};

#include <iostream>
int main() {
    MinStack ms;
    ms.push(3);
    ms.push(5);
    std::cout << ms.getMin() << " ";
    ms.push(2);
    ms.push(1);
    std::cout << ms.getMin() << " ";
    ms.pop();
    std::cout << ms.getMin() << " ";
    ms.pop();
    std::cout << ms.top() << " ";
    return 0;
}

A 3 1 2 5

B 3 1 3 5

C 3 2 2 5

D 3 1 2 3

💡 Hint

Track the minimum values pushed and popped carefully.

The min stack keeps track of minimums. After pushing 3 and 5, min is 3. After pushing 2 and 1, min is 1. Popping once removes 1, min becomes 2. Popping again removes 2, top is 5.

❓ Predict Output

intermediate

Resulting Min Stack State After Operations

After executing the following operations on a Min Stack, what is the value returned by getMin()?

DSA C++

MinStack ms;
ms.push(10);
ms.push(20);
ms.push(5);
ms.pop();
ms.push(7);
ms.pop();
ms.pop();
return ms.getMin();

A 20

B 5

C 7

D 10

💡 Hint

Remember to update min when popping elements.

Push 10 (min=10), push 20 (min=10), push 5 (min=5), pop removes 5 (min=10), push 7 (min=7), pop removes 7 (min=10), pop removes 20 (min=10). So min is 10.

🔧 Debug

advanced

Identify the Bug in Min Stack Implementation

What error will the following Min Stack code produce when pop() is called on an empty stack?

DSA C++

#include <stack>
class MinStack {
private:
    std::stack<int> s, minS;
public:
    void push(int x) {
        s.push(x);
        if(minS.empty() || x <= minS.top()) {
            minS.push(x);
        }
    }
    void pop() {
        if(s.top() == minS.top()) {
            minS.pop();
        }
        s.pop();
    }
    int top() {
        return s.top();
    }
    int getMin() {
        return minS.top();
    }
};

int main() {
    MinStack ms;
    ms.pop();
    return 0;
}

A std::out_of_range exception

B No error, runs fine

C Segmentation fault (access violation)

D std::underflow_error exception

💡 Hint

Consider what happens when calling top() or pop() on an empty stack.

Calling top() or pop() on an empty std::stack causes undefined behavior, often a segmentation fault.

🧠 Conceptual

advanced

Space Complexity of Min Stack Design

What is the worst-case space complexity of a Min Stack implemented with two stacks (one for values, one for minimums) when pushing n elements?

A O(n)

B O(n^2)

C O(log n)

D O(1)

💡 Hint

Consider how many elements can be stored in the min stack in the worst case.

In the worst case, every pushed element is smaller or equal to the current minimum, so min stack stores all n elements, resulting in O(n) space.

🚀 Application

expert

Using Min Stack to Find Minimum in Sliding Window

Given a Min Stack implementation, which approach correctly uses it to find the minimum in every sliding window of size k over an array of integers?

A Push all elements once; getMin() after each push gives minimum for all windows.

B Push elements of the window into Min Stack and pop elements leaving the window; getMin() gives current window minimum.

C Use Min Stack to store indices; pop indices outside window; top index corresponds to minimum element.

D Push elements and their counts; pop when count reaches zero; getMin() gives minimum.

💡 Hint

Think about how to maintain the window elements in the stack and update minimum accordingly.

By pushing elements entering the window and popping those leaving, the Min Stack always holds current window elements, so getMin() returns the window minimum.

Practice

1. What is the main purpose of a Min Stack data structure?

easy

A. To store elements in a queue fashion

B. To retrieve the minimum element in constant time

C. To sort elements in ascending order

D. To reverse the order of elements

Solution

1. Step 1: Understand the Min Stack concept

   A Min Stack is designed to keep track of the minimum element efficiently.

2. Step 2: Identify the key feature

   It allows retrieving the minimum element in constant time, unlike a normal stack.

3. Final Answer:

   To retrieve the minimum element in constant time -> Option B

4. Quick Check:

   Min Stack purpose = retrieve minimum element fast [OK]

Hint: Min Stack always tracks minimum for O(1) retrieval [OK]

Common Mistakes:

• Confusing Min Stack with sorting
• Thinking it behaves like a queue
• Assuming it reverses elements

2. Which of the following is the correct way to declare a stack of integers in C++?

easy

A. stack<int> s[];

B. stack s<int>;

C. stack<int> s;

D. stack<int> s()

Solution

1. Step 1: Recall C++ stack declaration syntax

   The correct syntax uses template with angle brackets and variable name after.

2. Step 2: Check each option

   stack<int> s; matches correct syntax: stack<int> s;. Others have syntax errors.

3. Final Answer:

   stack<int> s; -> Option C

4. Quick Check:

   C++ stack declaration = stack<int> s; [OK]

Hint: Use template syntax: stack<Type> variable; [OK]

Common Mistakes:

• Placing variable name inside angle brackets
• Using parentheses instead of semicolon
• Declaring as array without initialization

3. Consider the following C++ code snippet implementing a Min Stack push operation:

void push(int x) {
  s.push(x);
  if (minStack.empty() || x <= minStack.top()) {
    minStack.push(x);
  }
}

What will be the content of minStack after pushing the sequence [3, 5, 2, 2, 4]?

medium

A. [3, 5, 2, 2, 4]

B. [2, 2]

C. [3, 2]

D. [3, 2, 2]

Solution

1. Step 1: Trace push operations on minStack

   Push 3: minStack empty, push 3 -> [3] Push 5: 5 > top(3), no push -> [3] Push 2: 2 <= 3, push 2 -> [3, 2] Push 2: 2 <= 2, push 2 -> [3, 2, 2] Push 4: 4 > 2, no push -> [3, 2, 2]

2. Step 2: Confirm final minStack content

   minStack contains [3, 2, 2] after all pushes.

3. Final Answer:

   [3, 2, 2] -> Option D

4. Quick Check:

   minStack after pushes = [3, 2, 2] [OK]

Hint: Push to minStack only if new value ≤ current min [OK]

Common Mistakes:

• Pushing all elements to minStack
• Not pushing duplicates of min
• Confusing minStack with main stack

4. The following code snippet is intended to implement the pop() operation of a Min Stack. Identify the error:

void pop() {
  if (s.top() == minStack.top()) {
    minStack.pop();
  }
  s.pop();
}

medium

A. It does not check if stacks are empty before popping

B. It pops from minStack before popping from s, causing mismatch

C. It compares values incorrectly using == instead of <=

D. It should pop from s twice when values match

Solution

1. Step 1: Analyze pop operation safety

   The code pops from stacks without checking if they are empty, risking runtime errors.

2. Step 2: Identify missing safety checks

   Before calling top() or pop(), stacks should be checked for emptiness.

3. Final Answer:

   It does not check if stacks are empty before popping -> Option A

4. Quick Check:

   Pop safety requires empty checks [OK]

Hint: Always check stack empty before pop or top [OK]

Common Mistakes:

• Ignoring empty stack checks
• Misusing comparison operators
• Popping stacks in wrong order

5. You want to design a Min Stack that supports push, pop, top, and getMin all in O(1) time. Which approach below correctly achieves this with minimal extra space?

hard

A. Use one stack to store values and a second stack to store minimums only when a new minimum is pushed

B. Use one stack and sort it after each push to find minimum

C. Use two stacks: one for values and one for all values pushed, then find min by scanning

D. Use a queue to store values and a stack to store minimums

Solution

1. Step 1: Understand O(1) min retrieval requirement

   To get minimum in constant time, we must track minimums during push/pop without scanning.

2. Step 2: Evaluate approaches

   Use one stack to store values and a second stack to store minimums only when a new minimum is pushed uses a second stack to store minimums only when a new minimum appears, saving space and ensuring O(1) operations.

3. Final Answer:

   Use one stack to store values and a second stack to store minimums only when a new minimum is pushed -> Option A

4. Quick Check:

   Min Stack with minimal space = two stacks, min pushed selectively [OK]

Hint: Push min only when new min found to save space [OK]

Common Mistakes:

• Sorting stack after each push (slow)
• Scanning stack to find min (not O(1))
• Using queue which breaks stack order