Min Stack Design in DSA C++ - Build from Scratch

Min Stack Design

📖 Scenario: You are building a special stack for a game score tracker. This stack not only stores scores but also quickly tells the smallest score so far. This helps players see their lowest score instantly.

🎯 Goal: Create a MinStack class that supports push, pop, top, and getMin operations efficiently.

📋 What You'll Learn

Create a class called MinStack with private members for stack storage.

Implement push(int val) to add a value to the stack.

Implement pop() to remove the top value from the stack.

Implement top() to return the top value without removing it.

Implement getMin() to return the smallest value in the stack at any time.

Use an auxiliary stack to keep track of minimum values.

💡 Why This Matters

🌍 Real World

Min stacks are useful in scenarios where you need quick access to the smallest element, such as in game score tracking, stock price monitoring, or undo operations.

💼 Career

Understanding min stack design helps in interviews and real-world coding tasks where efficient data retrieval is critical.

1

Create the MinStack class with two stacks

Create a class called MinStack with two private std::stack<int> members named stackData and stackMin. Also add a public constructor MinStack().

DSA C++

class MinStack {
private:
    std::stack stackData;
    std::stack stackMin;
public:
    MinStack() {
        // Your code here
    }
};

Hint

Use std::stack<int> for both stacks and define them as private members.

2

Implement the push method

Add a public method void push(int val) to the MinStack class. It should push val onto stackData. Also, push val onto stackMin if stackMin is empty or val is less than or equal to the top of stackMin. Otherwise, push the current top of stackMin again.

DSA C++

class MinStack {
private:
    std::stack stackData;
    std::stack stackMin;
public:
    MinStack() {
        // Constructor does not need to do anything
    }
    
    void push(int val) {
        // Your code here
    }
};

Hint

Push val to stackData. For stackMin, push val if empty or smaller, else push the current minimum again.

3

Implement pop and top methods

Add public methods void pop() and int top() to the MinStack class. pop() should remove the top elements from both stackData and stackMin. top() should return the top element of stackData without removing it.

DSA C++

class MinStack {
private:
    std::stack stackData;
    std::stack stackMin;
public:
    MinStack() {
        // Constructor does not need to do anything
    }
    
    void push(int val) {
        stackData.push(val);
        if (stackMin.empty() || val <= stackMin.top()) {
            stackMin.push(val);
        } else {
            stackMin.push(stackMin.top());
        }
    }
    
    void pop() {
        // Your code here
    }
    
    int top() {
        // Your code here
    }
};

Hint

Pop from both stacks in pop(). Return top of stackData in top().

4

Implement getMin and test the MinStack

Add a public method int getMin() to the MinStack class that returns the top element of stackMin. Then, in main(), create a MinStack object, push the values 5, 3, 7, 3, pop once, and print the results of top() and getMin() separated by a space.

DSA C++

class MinStack {
private:
    std::stack stackData;
    std::stack stackMin;
public:
    MinStack() {
        // Constructor does not need to do anything
    }
    
    void push(int val) {
        stackData.push(val);
        if (stackMin.empty() || val <= stackMin.top()) {
            stackMin.push(val);
        } else {
            stackMin.push(stackMin.top());
        }
    }
    
    void pop() {
        stackData.pop();
        stackMin.pop();
    }
    
    int top() {
        return stackData.top();
    }
    
    int getMin() {
        // Your code here
    }
};

int main() {
    MinStack minStack;
    // Your code here
    return 0;
}

Hint

Return the top of stackMin in getMin(). In main(), push the values, pop once, then print top() and getMin().

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