Min Stack

Design a stack that supports these operations, each in O(1) time:

push(x): push x onto the stack
pop(): remove and return the top element
top(): return the top element
getMin(): return the smallest element currently in the stack

Example

Text

push(5), push(2), push(8)
getMin() -> 2,  top() -> 8
pop(), pop()               (removes 8, then 2)
getMin() -> 5             (the minimum goes back to 5 once 2 is gone)

The difficulty is the last step: after a pop, the stack has to know what the minimum was before the popped element was pushed.

Brute force: scan for the minimum

Store the elements in an ArrayList<Integer> and compute the minimum with a scan whenever it's asked for.

Java

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

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

        void push(int x) {
            items.add(x);
        }

        OptionalInt pop() {
            if (items.isEmpty()) return OptionalInt.empty();
            return OptionalInt.of(items.remove(items.size() - 1)); // remove(int index)
        }

        OptionalInt top() {
            return items.isEmpty() ? OptionalInt.empty() : OptionalInt.of(items.get(items.size() - 1));
        }

        OptionalInt getMin() { // O(n)
            int best = 0;
            boolean found = false;
            for (int x : items) {
                if (!found || x < best) {
                    best = x;
                    found = true;
                }
            }
            return found ? OptionalInt.of(best) : OptionalInt.empty();
        }
    }

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

Output

OptionalInt[2] OptionalInt[8]
OptionalInt[5]

Time: getMin is O(n), and everything else is O(1) (ArrayList.remove(size - 1) removes the last element without shifting). Space: O(n).

Keeping a single min field does not fix this. After popping the current minimum, the stack would have to rescan to find the new one.

Optimal: store the minimum with each value

Each entry stores its value and the minimum of all entries at or below it. That second number never changes after the push, because only entries above it can be added or removed. So the minimum of the whole stack is always stored in the top entry, and popping automatically brings back the previous minimum.

Walkthrough:

operation	stack after (bottom → top) as (value, min)	getMin
push 5	(5, 5)	5
push 2	(5, 5), (2, 2)	2
push 8	(5, 5), (2, 2), (8, 2)	2
pop	(5, 5), (2, 2)	2
pop	(5, 5)	5

Java

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

public class Main {
    static class MinStack {
        // each entry: {value, minimum of this entry and everything below it}
        private final Deque<int[]> items = new ArrayDeque<>();

        void push(int x) {
            OptionalInt current = getMin();
            int min = current.isPresent() ? Math.min(current.getAsInt(), x) : x;
            items.push(new int[]{x, min});
        }

        OptionalInt pop() {
            int[] entry = items.poll(); // null when empty
            return entry == null ? OptionalInt.empty() : OptionalInt.of(entry[0]);
        }

        OptionalInt top() {
            int[] entry = items.peek();
            return entry == null ? OptionalInt.empty() : OptionalInt.of(entry[0]);
        }

        OptionalInt getMin() {
            int[] entry = items.peek();
            return entry == null ? OptionalInt.empty() : OptionalInt.of(entry[1]);
        }
    }

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

Output

OptionalInt[2] OptionalInt[8]
OptionalInt[5] OptionalInt[5]
OptionalInt.empty

Time: O(1) for every operation. Space: O(n), with one extra int per entry.

Storing a two-element int[] in a single ArrayDeque keeps each value and its minimum together, so they cannot get out of sync, which can happen with two separate stacks. OptionalInt is a container that holds either one int or nothing. Returning it covers top, pop, and getMin on an empty stack. ArrayDeque.push, pop, and peek work at the top (the head) of the deque. peek and poll return null when it is empty, while pop throws NoSuchElementException.

Variant: a second stack that only stores new minimums

If many values are pushed but the minimum rarely changes, store minimums in a separate stack, and push onto it only when a value is less than or equal to the current minimum. When popping, pop the minimum stack too if the popped value equals its top.

Java

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

public class Main {
    static class MinStack {
        private final Deque<Integer> items = new ArrayDeque<>();
        private final Deque<Integer> mins = new ArrayDeque<>();

        void push(int x) {
            items.push(x);
            if (mins.isEmpty() || x <= mins.peek()) {
                mins.push(x);
            }
        }

        OptionalInt pop() {
            if (items.isEmpty()) return OptionalInt.empty();
            int x = items.pop();
            if (!mins.isEmpty() && mins.peek() == x) { // unboxes, compares int values
                mins.pop();
            }
            return OptionalInt.of(x);
        }

        OptionalInt getMin() {
            return mins.isEmpty() ? OptionalInt.empty() : OptionalInt.of(mins.peek());
        }
    }

    public static void main(String[] args) {
        MinStack s = new MinStack();
        for (int x : new int[]{5, 2, 8, 2}) {
            s.push(x);
        }
        s.pop();
        System.out.println(s.getMin()); // one 2 remains
        s.pop();
        s.pop();
        System.out.println(s.getMin());
    }
}

Output

OptionalInt[2]
OptionalInt[5]

The <= matters: if the same minimum is pushed twice, it has to be recorded twice, so that popping one copy doesn't lose the other.