Stack Design — Min/Max Stack (O(1))

What does it solve?

A normal stack gives push, pop, top in O(1), but finding the minimum means scanning everything: O(N). The Min Stack keeps getMin at O(1) too.

Key insight: keep a second min-stack in lockstep with the main stack. When you push x, push min(x, currentMin) onto the min-stack. Now the min-stack's top is always the minimum of everything currently in the main stack. On pop, pop both. Every operation touches only the tops → all O(1). The same trick with max(x, currentMax) gives a Max Stack.

The core idea

// parallel min-stack, top = current min
push(x):
main.push(x)
min.push(min(x, min.top() or +∞))
pop(): main.pop(); min.pop()
getMin(): return min.top()

Complexity

Time complexity

O(1)

push, pop, top, and getMin each touch only the top of one or two stacks. No scans, no loops, ever.

Space complexity

O(N)

The auxiliary min-stack mirrors the main stack's depth. A value-encoding trick can shave this, but the parallel stack is the clear, interview-safe version.

Operation sequences & edge cases

Live animation — main stack and parallel min-stack move in lockstep

pushed popped top min-stack

Main stack top = —

stack base

Min stack min = —

stack base

op = — size = — getMin = — returned = —

Step — of —

operation

—

this step

top

—

main stack

getMin

—

O(1)

size

—

elements

Select a sequence and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	Operation	Main stack	Min stack	getMin	Returned

C++ implementation

min_stack.cpp

#include <bits/stdc++.h>
using namespace std;

// Min Stack: push, pop, top, getMin all O(1) via a parallel min-stack.
class MinStack {
    stack<int> s;      // the real data
    stack<int> mn;     // mn.top() = min of everything in s
public:
    void push(int x) {
        s.push(x);
        // carry forward the smaller of x and the current min
        mn.push(mn.empty() ? x : min(x, mn.top()));
    }
    void pop() { s.pop(); mn.pop(); }   // pop both in lockstep
    int  top() { return s.top(); }
    int  getMin() { return mn.top(); } // answer is always on top
};

int main() {
    MinStack st;
    st.push(5); st.push(3); st.push(7); st.push(2);
    cout << st.getMin() << "\n"; // 2
    st.pop();
    cout << st.getMin() << "\n"; // 3
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars