Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) aka constant time complexity for each function.

Follow up

How will you implement max stack?

Questions to Ask the Interviewer

Q: What should getMin() do on empty stack?
A: In this case, return -1.

Q: What should pop do on empty stack?
A: In this case, nothing.

Q: What should top() do on empty stack?
A: In this case, return -1

NOTE: If you are using your own declared global variables, make sure to clear

Solution

Method 1 - Using 2 Stacks

This is not all that difficult if you think about it. Regular stacks support push() and pop() functions. We need to add a new read-only property, Minimum. You can’t just add a new variable to track the minimum because when the stack is popped you wouldn’t be know how to update the minimum variable without scanning through all items in the stack which would require you to pop and re-push each item, which is downright ugly. So we need to keep some auxiliary list of the stack items so we can update the minimum variable after we pop items.

A clever way to do that is to use another stack that stores the minimum of all items in the stack. The minimum value is calculated when items are pushed to the stack and when items are popped from the stack we also pop from the minStack to reveal the new minimum value.

Let’s call this stack min_stack. This stack will always have the minimum value at the top. Modify ‘push’ and ‘pop’ operations as follows:

push:

  • If the element being pushed is less than the top element of min_stack then push it on ‘min_stack’ as well.
  • Else, push the top element of ‘min_stack’ again on min_stack.

pop:

  • Every time you pop an element from the original stack, pop from min_stack as well.

Example Run

Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2

original_stack        min_stack
2                        1
1                        1
9                        3
8                        3
5                        3
3                        3
7                        7

You can see that at any stage, the min_stack can be queried for the minimum element in the stack.

Code

Java
class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();
    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int element) {
        stack.push(element);
        if (minStack.size() == 0 || element <= minStack.peek()) {
            minStack.push(element);
        } else {
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        minStack.pop();
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

Method 2 - Using LinkedList Like Structure and Pair

To make constant time of getMin(), we need to keep track of the minimum element for each element in the stack. Define an element class that holds element value, min value, and pointer to elements below it. We have to create a linked list with current value and min value like we had in the table in solution 1. Element = {value, min value till now}

Example Run

Again elements are pushed: 7 3 5 8 9 1 2

original_value            min_value
2                             1
1                             1
9                             3
8                             3
5                             3
3                             3
7                             7

LinkedList = (7, 7) -> (3, 3) -> (5, 3) and so on.

Code

Java
class Elem {
    public int value;
    public int min;
    public Elem next;

    public Elem(int value, int min) {
        this.value = value;
        this.min = min;
    }
}

public class MinStack {
    public Elem top;

    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        if (top == null) {
            top = new Elem(x, x);
        } else {
            Elem e = new Elem(x, Math.min(x, top.min));
            e.next = top;
            top = e;
        }

    }

    public void pop() {
        if (top == null)
            return;
        Elem temp = top.next;
        top.next = null;
        top = temp;

    }

    public int top() {
        if (top == null)
            return -1;
        return top.value;
    }

    public int getMin() {
        if (top == null)
            return -1;
        return top.min;
    }
}