Start learning free

LESSON 394 OF 536 · STACK

Min Stack in Java: Constant-Time getMin with Two Stacks

Practice O(1) Read the full explanation

A stack hands its values back in the opposite order they arrived: the last value pushed is the first one popped. Design a stack that can also say, at any moment, which value is the smallest of all the values it holds, and do every operation in constant time.

Implement the class MinStack:

  • MinStack() creates an empty stack.
  • push(val) puts the integer val on top of the stack.
  • pop() removes the value on top of the stack.
  • top() returns the value on top of the stack, without removing it.
  • getMin() returns the smallest value in the stack, without removing anything.

The input is a list of operations, applied in order to one new MinStack. The output lists what the top and getMin calls return, in order. The starter code spells these names the way your language does.

 

Example 1:

Input:
    push(-2)
    push(0)
    push(-3)
    getMin()
    pop()
    top()
    getMin()
Output: -3 0 -2
Explanation:
After the three pushes the stack holds -2, 0 and -3, with -3 on top, so the smallest value is -3.
pop() removes -3. Now 0 is on top, and the smallest value is -2 again: when the minimum leaves,
the minimum from before it arrived comes back.

Example 2:

Input:
    push(5)
    push(5)
    push(7)
    getMin()
    pop()
    pop()
    getMin()
    top()
Output: 5 5 5
Explanation: 5 is pushed twice. The two pops remove 7 and one of the 5s, but the other 5 is still in the stack, so the smallest value is still 5.

Example 3:

Input:
    push(3)
    top()
    getMin()
    push(1)
    push(2)
    top()
    getMin()
    pop()
    pop()
    getMin()
Output: 3 3 2 1 3
Explanation: The value on top (2) and the smallest value (1) can be different values. Once 2 and 1 are popped, only 3 is left, and it is the smallest again.

 

Constraints:

  • -231 <= val <= 231 - 1
  • pop, top and getMin are only called when the stack is not empty.
  • At most 2 * 105 calls in total are made to push, pop, top and getMin.

Note:

Each operation should run in O(1) time. Looking through the whole stack for its smallest value in getMin would take O(n) time per call, where n is the number of values in the stack.

STEP 1 OF 9
    Ctrl + Enter to check

    JAVA · STACK

    Min Stack in Java, explained

    Problem overview

    A stack gives values back in the opposite order they arrived: the last value pushed is the first one popped. The task is to build a MinStack class with four operations: push(val), pop(), top() and getMin(). The last one must return the smallest value currently in the stack, and every operation has to run in constant time, O(1).

    Take the first example: push -2, push 0, push -3. The stack now holds -2, 0 and -3, with -3 on top, so getMin() gives -3. After pop() removes -3, the value on top is 0 and the smallest value is -2 again. The outputs are -3 0 -2.

    The second example shows duplicates: after pushing 5, 5 and 7 and popping twice, one 5 is still in the stack, so the minimum is still 5.

    Approach: remember the minimum under every value

    The obvious way to answer getMin() is to look through the whole stack, which costs O(n) per call. Keeping a single variable min is quicker but breaks as soon as the minimum is popped: the stack then has to find the second smallest value, and a single number can't tell it.

    The way out is an observation about stacks. A value leaves the stack only after every value above it has left. While it is in the stack, the values below it can't change. So the minimum of "this value and everything below it" is fixed at the moment the value is pushed, and it can be written down once.

    The class therefore keeps two stacks of the same height. stack holds the values. minStack holds, at each depth, the smallest value from the bottom of the stack up to that depth. The top of minStack always describes the whole stack as it is now, so getMin() only has to read it. Popping from both stacks together uncovers the minimum the stack had before the popped value arrived.

    Here are the two stacks after each push in the first example, copied from a run of the solution below:

    OperationstackminStack
    push(-2)[-2][-2]
    push(0)[-2, 0][-2, -2]
    push(-3)[-2, 0, -3][-2, -2, -3]
    pop()[-2, 0][-2, -2]

    The bottom of each list is on the left and the top is on the right. After the pop, the top of minStack is -2 again, with no searching at all.

    Step by step

    1. Declare the value stack as a field of type Stack<Integer>, created with new Stack<>().
    2. Declare minStack the same way. Its entry at each depth is the smallest of the value at that depth and everything below it.
    3. In push, push val onto stack first, like on any stack.
    4. Start currentMin at val. If the stack was empty, val is its only value and so its minimum.
    5. If minStack isn't empty, lower currentMin with Math.min against the top of minStack. That top is already the smallest of everything under val, so one comparison is enough.
    6. Push currentMin onto minStack. Both stacks now have the same size. Equal values are pushed too, so a minimum that was pushed twice is remembered twice.
    7. In pop, pop from both stacks. They must stay the same size.
    8. In top, return stack.peek(), which reads the top without removing it.
    9. In getMin, return minStack.peek().

    The solution in Java

    class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public void push(int val) {
        stack.push(val);
        int currentMin = val;
        if (!minStack.isEmpty()) {
            currentMin = Math.min(currentMin, minStack.peek());
        }
        minStack.push(currentMin);
    }

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

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

    public int getMin() {
        return minStack.peek();
    }
}

    The Java details worth a closer look:

    • Stack<Integer> and unboxing. A Stack holds objects, so the int values are boxed into Integer. Math.min(currentMin, minStack.peek()) and return stack.peek() unbox them back to int automatically. If you compare two boxed values yourself, use equals or unbox first: with two Integer objects holding 1000, == gives false and equals gives true, because == compares references.
    • push, pop and peek all work at the top. java.util.Stack adds to and removes from the end of its internal list. peek() reads the top; only pop() removes it.
    • Empty stacks throw. pop() and peek() on an empty Stack throw java.util.EmptyStackException. The lesson only calls pop, top and getMin on a non-empty stack, so the code needs no guard.
    • Stack is an older class. It is built on Vector, and Java's own documentation recommends Deque for new code. ArrayDeque offers push, pop and peek too, but at the front: push(4) then push(9) prints as [9, 4], with 9 on top. Either works here. The lesson uses Stack because its method names match the problem.
    • No constructor needed. The fields are initialised where they are declared, so the default constructor already gives the empty MinStack the statement asks for.

    Complexity

    Time: O(1) per operation. push does two pushes, one comparison and one peek. pop does two pops. top and getMin each do one peek. Pushing to the end of a Stack is amortised constant, because the underlying array occasionally doubles.

    Space: O(n). For n values in the stack, minStack holds exactly n extra entries, one per value.

    Edge cases and common mistakes

    • Keeping one min variable. It is wrong after the minimum is popped, because nothing remembers the previous minimum.
    • Skipping duplicates in minStack. Pushing to minStack only when the value is a new minimum is a common variation, but then pop must compare before popping. The lesson avoids that by pushing an entry every time, which keeps the two stacks aligned. With 5, 5, 7 and two pops, the code returns 5 for the minimum.
    • Popping only one stack. The stacks fall out of step, and getMin then describes the wrong depth.
    • Comparing with top(). The top value and the minimum are different things. After pushing 3, 1 and 2, top() is 2 and getMin() is 1.
    • Extreme values. Pushing Integer.MIN_VALUE and then Integer.MAX_VALUE gives a top() of 2147483647 and a getMin() of -2147483648. Math.min compares and never subtracts, so nothing overflows.

    Testing

    • Push -2, 0, -3, then getMin(), pop(), top(), getMin() gives -3 0 -2.
    • Push 5, 5, 7, then getMin(), pop(), pop(), getMin(), top() gives 5 5 5.
    • Push 3, then top(), getMin(), push 1, push 2, then top(), getMin(), pop(), pop(), getMin() gives 3 3 2 1 3.
    • Push Integer.MIN_VALUE and Integer.MAX_VALUE, then top() and getMin() give 2147483647 -2147483648.
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free