Min Stack

NeetCode: Min Stack · LeetCode: 155. Min Stack · Difficulty: Medium

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

Brute force: scan for the minimum

A plain ArrayList gives O(1) push, pop, and top (the stack top is the last element, so remove(size - 1) shifts nothing), but getMin has to look at every element.

Java

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

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 = items.get(0);
        for (int v : items) {
            min = Math.min(min, v);
        }
        return min;
    }
}

public class Main {
    public static void main(String[] args) {
        MinStack s = new MinStack();
        s.push(1);
        s.push(2);
        s.push(0);
        System.out.println(s.getMin());
        s.pop();
        System.out.println(s.top() + " " + s.getMin());
    }
}

Output

0
2 1

Time: O(n) for getMin. Space: O(n).

Optimal: store the minimum with every value

Each entry stores a pair: the value and the minimum of the stack up to and including it. The pair is a two-element int[] held in an ArrayDeque, which is used as a stack through push, pop, and peek. The minimum of the whole stack is then the second half of the top entry, and popping automatically restores the previous minimum.

Java

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

class MinStack {
    private final Deque<int[]> items = new ArrayDeque<>(); // each entry is {value, minimum so far}

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

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

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

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

public class Main {
    public static void main(String[] args) {
        MinStack s = new MinStack();
        s.push(1);
        s.push(2);
        s.push(0);
        System.out.println(s.getMin());
        s.pop();
        System.out.println(s.top() + " " + s.getMin());
    }
}

Output

0
2 1

Time: O(1) for every operation. Space: O(n), two integers per element.