Min Stack

Medium Problem 35 of 151 Java and Python

Problem

Design a stack that supports push, pop, top and retrieving the minimum element, each in constant time.

Implement MinStack(), push(val), pop(), top() and getMin(). pop, top and getMin are only called on a non-empty stack.

Example 1

Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: -3, then 0, then -2
Why: After popping -3, the minimum goes back to -2.

Constraints

-2³¹ ≤ val ≤ 2³¹ – 1
At most 3 × 10⁴ calls in total.

Explanation

The hard part is pop: if you remove the current minimum, what is the new one? Rescanning costs O(n).

Notice that the minimum only depends on what is below each element. So when you push, also store the minimum of the stack at that moment. Popping then reveals the previous minimum for free.

Approach 1 · Naive

Scan for the minimum

Time O(1) push/pop/top, O(n) getMin
Space O(n)

Use a normal list as the stack and scan it whenever getMin is called.

push, pop and top work on the end of a list.
getMin loops over the list.

Java

import java.util.*;

class MinStack {
    private final List<Integer> items = new ArrayList<>();

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

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

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

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

Python

class MinStack:
    def __init__(self):
        self.items = []

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

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

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

    def getMin(self) -> int:
        return min(self.items)

Approach 2 · Optimal

Store the running minimum with each value

Time O(1) for every operation
Space O(n)

Each stack entry is a pair: the value and the minimum of the stack up to and including it.

push(val): the new minimum is min(val, current min); push (val, newMin).
pop(): pop the top pair.
top() and getMin(): read the top pair's value or minimum.

Java

import java.util.*;

class MinStack {
    // Each entry is { value, minimum of the stack up to here }.
    private final Deque<int[]> stack = new ArrayDeque<>();

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

    public void pop() {
        stack.pop();
    }

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

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

Python

class MinStack:
    def __init__(self):
        self.stack = []  # (value, minimum up to here)

    def push(self, val: int) -> None:
        low = min(val, self.stack[-1][1]) if self.stack else val
        self.stack.append((val, low))

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

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

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

Complexity compared

Approach	Time	Space
Naive Scan for the minimum	O(1) push/pop/top, O(n) getMin	O(n)
Optimal Store the running minimum with each value	O(1) for every operation	O(n)

Key takeaways

When a query depends only on what came before, store its answer at each step.
A space-saving variant keeps a second stack that only pushes when a new minimum arrives.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem