Min Stack Design in DSA C++

Mental Model

A Min Stack keeps track of the smallest value at every point so we can get the minimum quickly.

Analogy: Imagine a stack of plates where each plate has a note showing the smallest plate below it. When you add or remove plates, you update the note so you always know the smallest plate on top.

Stack top -> [value: 3, min: 1] -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Dry Run Walkthrough

Input: Operations: push(5), push(1), push(3), getMin(), pop(), getMin()

Goal: Show how the stack keeps track of minimum values after each operation

Step 1: push 5 onto stack

Top -> [value: 5, min: 5] -> null

Why: First element is the minimum itself

Step 2: push 1 onto stack

Top -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: 1 is smaller than previous min 5, so min updates to 1

Step 3: push 3 onto stack

Top -> [value: 3, min: 1] -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: 3 is bigger than current min 1, so min stays 1

Step 4: getMin returns 1

Top -> [value: 3, min: 1] -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: Minimum is stored at top node

Step 5: pop top element (3)

Top -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: Removing 3 reveals previous min 1

Step 6: getMin returns 1

Top -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: Minimum remains 1 after pop

Result:

Top -> [value: 1, min: 1] -> [value: 5, min: 5] -> null
getMin = 1

Annotated Code

DSA C++

#include <iostream>
#include <stack>
#include <algorithm>
#include <utility>
using namespace std;

class MinStack {
private:
    stack<pair<int, int>> st; // pair: (value, current min)

public:
    void push(int val) {
        int current_min = st.empty() ? val : min(val, st.top().second);
        st.push({val, current_min});
    }

    void pop() {
        if (!st.empty()) {
            st.pop();
        }
    }

    int top() {
        if (!st.empty()) {
            return st.top().first;
        }
        return -1; // or throw error
    }

    int getMin() {
        if (!st.empty()) {
            return st.top().second;
        }
        return -1; // or throw error
    }
};

int main() {
    MinStack minStack;
    minStack.push(5);
    minStack.push(1);
    minStack.push(3);
    cout << minStack.getMin() << "\n"; // expect 1
    minStack.pop();
    cout << minStack.getMin() << "\n"; // expect 1
    return 0;
}

int current_min = st.empty() ? val : min(val, st.top().second);

Calculate new min by comparing pushed value with current min

st.push({val, current_min});

Push value and current min as a pair onto stack

st.pop();

Remove top element, min updates automatically

return st.top().second;

Return current minimum from top element

Output

1

1

Complexity Analysis

Time: O(1) for push, pop, top, and getMin because all operations use stack top only

Space: O(n) because we store each element with its current min in the stack

vs Alternative: Compared to scanning entire stack for min (O(n)), this design is faster with O(1) min retrieval

Edge Cases

empty stack getMin or top

returns -1 as error indicator

DSA C++

if (!st.empty()) { return st.top().second; } return -1;

push duplicate minimum values

min stack correctly tracks min for each duplicate

DSA C++

int current_min = st.empty() ? val : min(val, st.top().second);

pop until empty

stack becomes empty safely without error

DSA C++

if (!st.empty()) { st.pop(); }

When to Use This Pattern

When you need to get the minimum value quickly from a stack at any time, use Min Stack pattern to track minimums alongside values.

Common Mistakes

Mistake: Only storing values without tracking minimums causes getMin to be O(n)
Fix: Store pairs of (value, current min) to keep getMin O(1)

Mistake: Updating min incorrectly by not comparing with previous min
Fix: Always compare new value with current min before pushing

Summary

Keeps track of minimum value in a stack with O(1) retrieval.

Use when you need fast minimum queries on a stack.

Store each element with the minimum value seen so far to update min efficiently.

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