Start practising

Min Stack (Stack)

Medium Stack Stack Basics Original on LeetCode

Min Stack is a medium stack problem solved with the stack basics pattern. The best approach, optimal (pair each value with the running minimum), runs in O(1) for every operation time and O(n) space. Below are 2 approaches in Java, from brute force (scan for the minimum) up.

Problem

Design a stack that supports push, pop, top and getMin (return the smallest element currently in the stack), all in O(1) time.

Examples

Example 1

Input
push(5), push(2), push(4), getMin(), pop(), pop(), getMin(), top()
Output
2, 5, 5
Why
After popping 4 and 2, only 5 remains.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • pop, top and getMin are only called on a non-empty stack.
  • Every operation must be O(1).

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute force (scan for the minimum)O(1), getMin O(n)O(n)
Optimal (pair each value with the running minimum)O(1) for every operationO(n)

1Brute force (scan for the minimum)

TimeO(1), getMin O(n)
SpaceO(n)

Use a normal stack and compute getMin by scanning every element.

  1. push, pop and top use the stack directly.
  2. getMin loops through all elements.
Java
class MinStack {
    private final Deque<Integer> st = new ArrayDeque<>();

    public void push(int val) { st.push(val); }
    public void pop() { st.pop(); }
    public int top() { return st.peek(); }

    public int getMin() {
        int min = Integer.MAX_VALUE;
        for (int x : st) min = Math.min(min, x);
        return min;
    }
}

2Optimal (pair each value with the running minimum)

TimeO(1) for every operation
SpaceO(n)

Push pairs of (value, minimum so far). The top pair always knows the minimum of the whole stack, and popping restores the previous minimum automatically.

  1. push: newMin = min(val, current min); push {val, newMin}.
  2. top returns top[0]; getMin returns top[1]; pop removes the pair.
Java
class MinStack {
    private final Deque<int[]> st = new ArrayDeque<>();

    public void push(int val) {
        int min = st.isEmpty() ? val : Math.min(val, st.peek()[1]);
        st.push(new int[] { val, min });
    }

    public void pop() { st.pop(); }
    public int top() { return st.peek()[0]; }
    public int getMin() { return st.peek()[1]; }
}

Edge cases to test

  • Pushing a value equal to the current minimum, then popping it
  • Integer.MIN_VALUE as a value

Hints

Hint 1

Store with each element the minimum of the stack at the moment it was pushed.

FAQ

What is the best time complexity for Min Stack?

Optimal (pair each value with the running minimum) runs in O(1) for every operation time and O(n) extra space.

Which pattern does Min Stack use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.

Is there a brute force solution for Min Stack?

Yes. Brute force (scan for the minimum) takes O(1), getMin O(n) time and O(n) space. Use a normal stack and compute getMin by scanning every element.

Which edge cases should I test for Min Stack?

Pushing a value equal to the current minimum, then popping it; Integer.MINVALUE as a value.