What is the brute force approach and complexity for Min Stack?

Plain vector stack; getMin scans every value with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Min Stack?

Each entry stores its value and the min of everything up to it with optimal time complexity O(1) and space complexity O(N).

How do you identify the pattern for Min Stack?

Look for key signals in the prompt: "push / pop / top" indicates Last in, first out: changes only ever happen at the top.; "getMin in O(1)" indicates We cannot scan, so the answer must be stored somewhere and ready to read.; "after a pop, the min may go back to an older value" indicates Old answers must be remembered in the same last-in, first-out order → store them in the stack itself..

Min Stack

Medium·LeetCode #155Basic Anchor

LeetCode

Jump:

30-Second Mental ModelStack simulation / design (stack of (value, min so far))

Complexity:O(N)→O(1)

Key Insight

Every entry on the stack is a pair (value, minSoFar), where minSoFar is the smallest value from the bottom of the stack up to and including this entry. push computes it from the entry below. getMin just reads the top entry's minSoFar. pop needs no extra work.

Core Validity Invariant

Every entry's minSoFar is the smallest value from the bottom of the stack up to that entry. Because entries below the top never change, this stays true for as long as the entry is on the stack.

Problem

Build a class MinStack: a normal stack that can also tell you its smallest value at any moment.

MinStack() creates an empty stack.
void push(int val) puts val on top.
void pop() removes the top value.
int top() returns the top value.
int getMin() returns the smallest value currently on the stack.

Every one of these must run in O(1) time.

Input

A sequence of calls to push, pop, top and getMin.

Output

The return value of each top and getMin call. push and pop return nothing.

Example 1

Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Output: -3, 0, -2 (the results of getMin, top, getMin)

With -2, 0, -3 on the stack the smallest is -3. After popping -3 the top is 0, and the smallest of what is left (-2, 0) is -2.

Constraints

• −2^31 ≤ val ≤ 2^31 − 1
• pop, top and getMin are only called when the stack is not empty
• At most 3 · 10^4 calls in total

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I keep one variable minVal, what goes wrong when the current minimum is popped?
2.
When a value is pushed, which values can it be compared with? Which values are below it, and do they ever change while it is on the stack?
3.
For a given entry, is "the smallest value from the bottom up to here" fixed, or can later pushes and pops change it?
4.
What happens if the same minimum value is pushed twice and then popped once?
5.
Which is the trade-off: extra memory for every entry, or extra memory only for some entries?

Brute force approach

Idea

Keep the values in a vector<int>. push, pop and top work on the back. For getMin, loop over the whole vector and return the smallest value.

Thinking process

1
push, pop and top are just a normal stack, so a vector does them in O(1).
2
getMin is the only new thing. The simplest way: look at every value and keep the smallest.
3
That is correct, but it costs O(n) on every getMin call.

Code & Implementation

brute.cpp

class MinStack {
    vector<int> st;   // st.back() is the top

public:
    MinStack() {}

    void push(int val) {
        st.push_back(val);
    }

    void pop() {
        st.pop_back();
    }

    int top() {
        return st.back();
    }

    int getMin() {
        // Look at every value currently on the stack.
        int best = st[0];
        for (int x : st) best = min(best, x);
        return best;
    }
};

import java.util.ArrayList;
import java.util.List;

class MinStack {
    private List<Integer> st; // st.get(st.size() - 1) is the top

    public MinStack() {
        st = new ArrayList<>();
    }

    public void push(int val) {
        st.add(val);
    }

    public void pop() {
        st.remove(st.size() - 1);
    }

    public int top() {
        return st.get(st.size() - 1);
    }

    public int getMin() {
        // Look at every value currently on the stack.
        int best = st.get(0);
        for (int x : st) {
            best = Math.min(best, x);
        }
        return best;
    }
}

class MinStack:
    def __init__(self):
        self.st: list[int] = []

    def push(self, val: int) -> None:
        self.st.append(val)

    def pop(self) -> None:
        self.st.pop()

    def top(self) -> int:
        return self.st[-1]

    def getMin(self) -> int:
        # Look at every value currently on the stack.
        best = self.st[0]
        for x in self.st:
            best = min(best, x)
        return best

export class MinStack {
    private st: number[];

    constructor() {
        this.st = [];
    }

    push(val: number): void {
        this.st.push(val);
    }

    pop(): void {
        this.st.pop();
    }

    top(): number {
        return this.st[this.st.length - 1];
    }

    getMin(): number {
        // Look at every value currently on the stack.
        let best = this.st[0];
        for (const x of this.st) {
            best = Math.min(best, x);
        }
        return best;
    }
}

Complexity

Time O(N)Space O(N)

With 3 · 10^4 calls, a stack of about 1.5 · 10^4 values and many getMin calls, this is around 2 · 10^8 steps. It is also not O(1), which the problem asks for. push, pop and top are O(1); getMin scans the stack, O(N).

Better approach

Why brute force is slow

Every getMin looks at all n values, even though the stack only changed at the top since the last call.

What repeated work are we doing?

The bottom part of the stack is the same between calls, so its minimum is recomputed again and again for nothing.

What information can we reuse?

Remember the minimums in a stack of their own. A new min is pushed on top of the old one, and when it is popped the old min is right there underneath.

New approach

Idea

Keep the normal stack, and a second stack mins whose top is always the current minimum. On push, also push onto mins if val <= mins.top(). On pop, if the value leaving equals mins.top(), pop mins too.

Thinking process

1
Brute force searches for the min again after every change, but a push or pop only changes one value.
2
A pushed value bigger than the current min can never become the min while that min sits below it. So I do not need to remember anything for it.
3
A pushed value that is smaller (or equal) becomes the new min. When it is popped later, the min goes back to the one before it. That is "last in, first out" again, so the mins themselves form a stack.
4
Equal values matter: if 3 is pushed twice, mins needs two copies of 3. Otherwise popping one 3 would remove the only 3 from mins while another 3 is still on the stack.

Visual

mins only gets a value when it is <= the current min. The orange cell is the duplicate 3: without <= it would be missing, and popping the second 3 would wrongly remove the only 3 from mins.

Two stacks with <=

push(5), push(3), push(7), getMin(), push(3), push(2), getMin(), pop(), getMin(), pop(), getMin(), pop(), top(), pop(), getMin()

step 1/15

calls

push(5)

push(3)

push(7)

getMin()

push(3)

push(2)

getMin()

pop()

getMin()

pop()

getMin()

pop()

top()

pop()

getMin()

▲i

stack

▲top

mins

▲top

Call

call: push(5)
current min: — (empty)
5 <= min?: empty → yes
pushed to mins: yes

push(5): new min → push on mins too

5 is the smallest so far, so it goes on both stacks.

Code & Implementation

better.cpp

class MinStack {
    stack<int> st;     // every value
    stack<int> mins;   // only the values that were a new minimum (or equal to it)

public:
    MinStack() {}

    void push(int val) {
        st.push(val);
        // <= (not <): a duplicate of the current min needs its own copy,
        // so popping one of them still leaves the other as the min.
        if (mins.empty() || val <= mins.top()) mins.push(val);
    }

    void pop() {
        // If the value leaving is the current min, that min leaves too.
        if (st.top() == mins.top()) mins.pop();
        st.pop();
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return mins.top();
    }
};

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    private Deque<Integer> st;     // every value
    private Deque<Integer> mins;   // only the values that were a new minimum (or equal to it)

    public MinStack() {
        st = new ArrayDeque<>();
        mins = new ArrayDeque<>();
    }

    public void push(int val) {
        st.push(val);
        // <= (not <): a duplicate of the current min needs its own copy,
        // so popping one of them still leaves the other as the min.
        if (mins.isEmpty() || val <= mins.peek()) {
            mins.push(val);
        }
    }

    public void pop() {
        // If the value leaving is the current min, that min leaves too.
        if (st.peek().equals(mins.peek())) {
            mins.pop();
        }
        st.pop();
    }

    public int top() {
        return st.peek();
    }

    public int getMin() {
        return mins.peek();
    }
}

class MinStack:
    def __init__(self):
        self.st: list[int] = []    # every value
        self.mins: list[int] = []  # only the values that were a new minimum (or equal to it)

    def push(self, val: int) -> None:
        self.st.append(val)
        # <= (not <): a duplicate of the current min needs its own copy,
        # so popping one of them still leaves the other as the min.
        if not self.mins or val <= self.mins[-1]:
            self.mins.append(val)

    def pop(self) -> None:
        # If the value leaving is the current min, that min leaves too.
        if self.st[-1] == self.mins[-1]:
            self.mins.pop()
        self.st.pop()

    def top(self) -> int:
        return self.st[-1]

    def getMin(self) -> int:
        return self.mins[-1]

export class MinStack {
    private st: number[];
    private mins: number[];

    constructor() {
        this.st = [];
        this.mins = [];
    }

    push(val: number): void {
        this.st.push(val);
        // <= (not <): a duplicate of the current min needs its own copy,
        // so popping one of them still leaves the other as the min.
        if (this.mins.length === 0 || val <= this.mins[this.mins.length - 1]) {
            this.mins.push(val);
        }
    }

    pop(): void {
        // If the value leaving is the current min, that min leaves too.
        if (this.st[this.st.length - 1] === this.mins[this.mins.length - 1]) {
            this.mins.pop();
        }
        this.st.pop();
    }

    top(): number {
        return this.st[this.st.length - 1];
    }

    getMin(): number {
        return this.mins[this.mins.length - 1];
    }
}

Complexity

Time O(1)Space O(N)

Already O(1) for every call. Its advantage is memory: if the minimum rarely changes (e.g. pushes like 1, 5, 9, 7, 8…), mins stays tiny. In the worst case (values pushed in decreasing order) it stores two values per entry, the same as the pair stack. The price is the <= and the equality check in pop, which are easy to get wrong. Every operation is O(1).

Optimized approach

Idea

Start from brute force

Brute force keeps a plain stack and, on every getMin, scans all the values to find the smallest.

Find the repeated work

Between two getMin calls only the top of the stack changed. The part below the top is the same, but brute force rescans it every time to find a minimum it already found before.

Define the state — what variables do I need?

st: stack<pair<int,int>>, bottom to top. Each entry is (value, minSoFar).
st.top().first: The current top value.
st.top().second: The smallest value on the whole stack right now.

Define validity

Every entry's minSoFar is the smallest value from the bottom of the stack up to that entry. Because entries below the top never change, this stays true for as long as the entry is on the stack.

Define the transitions — when does each pointer move, and why is it safe?

push(val), stack empty

push (val, val)

It is the only value, so it is also the smallest.

push(val), stack not empty

push (val, min(val, st.top().second))

st.top().second is the min of everything below. Adding one value changes the min only if that value is smaller.

pop()

st.pop()

The entry below was pushed before the popped one, so its minSoFar never included the popped value. It is already correct.

top() / getMin()

return st.top().first / st.top().second

The top entry's stored min covers the whole stack.

What does the current window add to the answer?

getMin returns the top entry's minSoFar; top returns its value. Each call reads one entry.

Code & Implementation

optimal.cpp

class MinStack {
    // Each entry: (value, smallest value from the bottom up to this entry).
    stack<pair<int, int>> st;

public:
    MinStack() {}

    void push(int val) {
        // The new entry's min is val or the min of everything below it.
        int curMin = st.empty() ? val : min(val, st.top().second);
        st.push({val, curMin});
    }

    void pop() {
        // The entry below already remembers its own min, so nothing to fix.
        st.pop();
    }

    int top() {
        return st.top().first;
    }

    int getMin() {
        return st.top().second;
    }
};

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    // Each entry: [value, smallest value from the bottom up to this entry].
    private Deque<int[]> st;

    public MinStack() {
        st = new ArrayDeque<>();
    }

    public void push(int val) {
        // The new entry's min is val or the min of everything below it.
        int curMin = st.isEmpty() ? val : Math.min(val, st.peek()[1]);
        st.push(new int[]{val, curMin});
    }

    public void pop() {
        // The entry below already remembers its own min, so nothing to fix.
        st.pop();
    }

    public int top() {
        return st.peek()[0];
    }

    public int getMin() {
        return st.peek()[1];
    }
}

class MinStack:
    # Each entry: (value, smallest value from the bottom up to this entry).
    def __init__(self):
        self.st: list[tuple[int, int]] = []

    def push(self, val: int) -> None:
        # The new entry's min is val or the min of everything below it.
        cur_min = val if not self.st else min(val, self.st[-1][1])
        self.st.append((val, cur_min))

    def pop(self) -> None:
        # The entry below already remembers its own min, so nothing to fix.
        self.st.pop()

    def top(self) -> int:
        return self.st[-1][0]

    def getMin(self) -> int:
        return self.st[-1][1]

export class MinStack {
    // Each entry: [value, smallest value from the bottom up to this entry].
    private st: [number, number][];

    constructor() {
        this.st = [];
    }

    push(val: number): void {
        // The new entry's min is val or the min of everything below it.
        const curMin = this.st.length === 0 ? val : Math.min(val, this.st[this.st.length - 1][1]);
        this.st.push([val, curMin]);
    }

    pop(): void {
        // The entry below already remembers its own min, so nothing to fix.
        this.st.pop();
    }

    top(): number {
        return this.st[this.st.length - 1][0];
    }

    getMin(): number {
        return this.st[this.st.length - 1][1];
    }
}

Complexity

Time O(1)Space O(N)

Always two ints per entry. The two-stack version can use less memory when the min rarely changes; both are O(N) in the worst case. We pick the pair stack as the one to remember because it has no tricky cases. In an interview, mention the two-stack version as a memory saving. Every operation is O(1).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Plain vector stack; getMin scans every value	O(N)	O(N)
Better	Main stack + a stack of mins pushed only when val <= current min	O(1)	O(N)
Optimal	Each entry stores its value and the min of everything up to it	O(1)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“push / pop / top”Last in, first out: changes only ever happen at the top.
“getMin in O(1)”We cannot scan, so the answer must be stored somewhere and ready to read.
“after a pop, the min may go back to an older value”Old answers must be remembered in the same last-in, first-out order → store them in the stack itself.

Changes only at the top+query about the whole stack+answer fixed per height→Stack simulation / design (stack of (value, min so far))

This is the anchor for the sub-pattern: the stack is not used to match or cancel anything, it is the thing being simulated, and each entry carries extra info computed from the entry below. Simplify Path and Asteroid Collision also simulate a process with a stack, but there new items actively remove old ones (.. pops a folder, a left-mover destroys right-movers). Here pops only come from the caller.

Don't make this mistake

Keeping a single minVal variable

✗ void push(int val) { st.push(val); minVal = min(minVal, val); } void pop() { st.pop(); } // what is the min now?

✓ st.push({val, st.empty() ? val : min(val, st.top().second)});

Pattern-confusion trap: this is not "running minimum of an array". An array only grows, but a stack also shrinks. When the current min is popped, one variable cannot tell you what the min was before it was pushed. You need to remember the min at every height.

Using < instead of <= in the two-stack version

✗ if (mins.empty() || val < mins.top()) mins.push(val);

✓ if (mins.empty() || val <= mins.top()) mins.push(val);

Push 3, then 3 again. With < only one 3 is in mins. Pop the second 3: it equals mins.top(), so mins is popped, and getMin now returns something bigger than 3 even though a 3 is still on the stack.

Forgetting to pop the mins stack

✗ void pop() { st.pop(); }

✓ void pop() { if (st.top() == mins.top()) mins.pop(); st.pop(); }

If the popped value was the current min, mins still reports it, so getMin returns a value that is no longer on the stack. Check before popping st, while you can still read the value.

Using the top value of the stack below instead of its stored min

✗ int curMin = min(val, st.top().first);

✓ int curMin = min(val, st.top().second);

st.top().first is just the last value pushed, not the smallest. Push 1, 5, 3: with .first the entry for 3 would store min(3, 5) = 3, but the real min is 1.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Expression Parser & Interpreter Pattern

Abstract syntax tree evaluation and operator precedence parsing.

Explore Track

C++ Internals

Stack vs Heap Segments

Call stack frame layout, return addresses, and buffer overflow prevention.

Explore Track

Simplify Path