☕ DSA Java Articles

Topics › Stacks and Queues › Learning

Implement Min Stack

Hard TUF ID 958 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Design a stack that, in addition to the usual push(x), pop() and top(), supports getMin(), which returns the smallest element currently in the stack. Every operation must run in O(1) time. The stack is last-in-first-out as usual; getMin must reflect exactly the elements that are still present, so popping a minimum must reveal the previous minimum.

Constraints: up to 3 × 10^4 operations, values in the full 32-bit int range [-2^31, 2^31 - 1]. pop, top and getMin are only called on a non-empty stack in the LeetCode version; the code here throws NoSuchElementException otherwise.

Example 1 (LeetCode 155)

push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
output: -3, 0, -2            // after -3 leaves, the minimum is -2 again

Example 2

push(2), push(1), push(1), getMin(), pop(), getMin(), pop(), getMin()
output: 1, 1, 2              // two copies of the minimum: popping one keeps the other

All three designs below implement this interface, so a single test script can run identical scripts against them:

interface MinStack {
    void push(int x);
    void pop();
    int top();
    int getMin();
}

Approach 1: Store the running minimum with every element

Intuition. Scanning the stack for the minimum on every getMin is O(n), and the whole point is to avoid that. Observe that the minimum of a stack depends only on what is below and including the top. If each entry remembers “the minimum of me and everything below me”, then the top entry’s remembered minimum is the answer, and popping automatically reveals the correct earlier minimum because the entry below carries its own.

Algorithm.

  1. Keep a stack of pairs {value, minSoFar}.
  2. push(x): minSoFar = x if the stack is empty, else min(x, top.minSoFar). Push {x, minSoFar}.
  3. pop(): pop the pair.
  4. top(): return top.value. getMin(): return top.minSoFar.
static class PairMinStack implements MinStack {
    private final Deque<int[]> stack = new ArrayDeque<>();   // each entry is {value, min of this entry and all below}

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

    public void pop() {
        if (stack.isEmpty()) throw new NoSuchElementException("stack underflow");
        stack.pop();
    }

    public int top() {
        if (stack.isEmpty()) throw new NoSuchElementException("stack is empty");
        return stack.peek()[0];
    }

    public int getMin() {
        if (stack.isEmpty()) throw new NoSuchElementException("stack is empty");
        return stack.peek()[1];
    }
}

Complexity. Time O(1) for each operation. Space O(n) pairs, that is 2n ints: twice the storage of a plain stack.

Dry run on example 1:

operation stack of {value, min} (bottom → top) returns
push(-2) {-2,-2}  
push(0) {-2,-2} {0,-2}  
push(-3) {-2,-2} {0,-2} {-3,-3}  
getMin()   -3
pop() {-2,-2} {0,-2}  
top()   0
getMin()   -2

Approach 2: A second stack of minimums only

Intuition. Most entries in approach 1 repeat the same minimum. We only need to remember a minimum at the moments it changes. Keep an auxiliary stack mins; push x onto it when x is a new minimum, and pop from it when the value being popped from the main stack is the current minimum. Then mins.peek() is always the minimum of the main stack.

The one subtlety is duplicates. If x equals the current minimum and we do not record it, then popping one copy would pop the single record and lose the minimum even though another copy remains. Using x <= mins.peek() (not <) records every copy.

Algorithm.

  1. push(x): push onto values; if mins is empty or x <= mins.peek(), push onto mins too.
  2. pop(): pop x from values; if x == mins.peek(), pop mins.
  3. top(): values.peek(). getMin(): mins.peek().
static class TwoStackMinStack implements MinStack {
    private final Deque<Integer> values = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();    // non-increasing from bottom to top

    public void push(int x) {
        values.push(x);
        if (mins.isEmpty() || x <= mins.peek()) mins.push(x);  // <= so that duplicate minimums are counted
    }

    public void pop() {
        if (values.isEmpty()) throw new NoSuchElementException("stack underflow");
        int x = values.pop();
        if (x == mins.peek()) mins.pop();                      // the popped value was the current minimum
    }

    public int top() {
        if (values.isEmpty()) throw new NoSuchElementException("stack is empty");
        return values.peek();
    }

    public int getMin() {
        if (mins.isEmpty()) throw new NoSuchElementException("stack is empty");
        return mins.peek();
    }
}

Complexity. Time O(1) per operation. Space O(n) in the worst case (a strictly decreasing push sequence puts every element on both stacks), but only n + k where k is the number of times a new minimum was pushed, which in practice is far less than 2n.

Approach 3: One stack, O(1) extra space, encoded minimums

Intuition. Can we get rid of the second stack altogether and keep just the current minimum in one variable? The problem is pop: when we pop the current minimum, we must recover the previous minimum, and with only one variable we have forgotten it. The trick is to hide the previous minimum inside the stack entry itself.

When pushing x that is smaller than the current min, do not store x. Store e = 2x - min instead and set min = x. Because x < min (the old one), we have e = x + (x - min) < x, so e is strictly less than the new minimum. That is the signal: an entry smaller than min cannot be a real value (real values are always >= min), so it must be an encoded one, and the real value it represents is min itself. To undo it on pop, solve e = 2x - oldMin for oldMin: since x is the current min, oldMin = 2 * min - e.

Values can be as low as -2^31, so 2x - min can be about -3 × 2^31, outside int. The stack stores long; getMin and top cast back to int, which is safe because the real values are always ints.

Algorithm.

  1. push(x): if the stack is empty, push x and set min = x. Else if x >= min, push x. Else push 2x - min and set min = x.
  2. pop(): pop t. If t < min, the entry was encoded: set min = 2 * min - t.
  3. top(): peek t. If t < min, the real value is min; otherwise it is t.
  4. getMin(): return min.
static class EncodedMinStack implements MinStack {
    private final Deque<Long> stack = new ArrayDeque<>();
    private long min;                        // valid whenever the stack is non-empty

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push((long) x);
            min = x;
        } else if (x >= min) {
            stack.push((long) x);            // ordinary value, stored as is
        } else {
            stack.push(2L * x - min);        // encoded: strictly less than the new minimum x
            min = x;
        }
    }

    public void pop() {
        if (stack.isEmpty()) throw new NoSuchElementException("stack underflow");
        long t = stack.pop();
        if (t < min) min = 2 * min - t;      // encoded entry: undo the encoding to recover the previous minimum
    }

    public int top() {
        if (stack.isEmpty()) throw new NoSuchElementException("stack is empty");
        long t = stack.peek();
        return (int) (t < min ? min : t);    // an encoded entry means the real value is the current minimum
    }

    public int getMin() {
        if (stack.isEmpty()) throw new NoSuchElementException("stack is empty");
        return (int) min;
    }
}

Dry run on example 1 (min shown after each step):

operation pushed / popped entry stack (bottom → top) min returns
push(-2) -2 (first) [-2] -2  
push(0) 0 ≥ -2, store 0 [-2, 0] -2  
push(-3) -3 < -2, store 2(-3)-(-2) = -4 [-2, 0, -4] -3  
getMin()     -3 -3
pop() -4 < -3 → min = 2(-3)-(-4) = -2 [-2, 0] -2  
top() 0 ≥ -2, real value   -2 0
getMin()     -2 -2

Complexity. Time O(1) per operation. Space O(n) for the single stack plus one long: no second stack and no pairs. The entries are long rather than int, so the per-element cost is the same 8 bytes as a pair of ints would be; the real saving is conceptual, and it becomes a true saving when the values are already 64-bit.

Edge cases and pitfalls