Min Stack

Problem

Design a stack that supports push, pop, top, and getMin all in O(1).

Constraints

• Methods called ≤ 3·10⁴ times
• −2³¹ ≤ value ≤ 2³¹ − 1

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

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

    def push(self, val):
        mn = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, mn))

    def pop(self):
        self.stack.pop()

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

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

Java

import java.util.Stack;

class MinStack {

    private Stack<int[]> stack = new Stack<>();

    public MinStack() { }

    public void push(int x) {

        /* If the stack is empty, then the min value
         * must just be the first value we add. */
        if (stack.empty()) {
            stack.push(new int[]{x, x});
            return;
        }

        int currentMin = stack.peek()[1];
        stack.push(new int[]{x, Math.min(x, currentMin)});
    }

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

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

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.