Min Stack

Problem Statement

LeetCode-155: 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)$ time complexity for each function.

Approach

A few things to note about the problem:

1. There can be duplicate elements in the stack. So we need to maintain the count of the elements as well.
2. We need to maintain the minimum element in the stack at all times as all the operations are supposed to complete in $O(1)$ time.

To implement a solution with above constraints, we can use two stacks. One stack will store the elements and the other stack will store the minimum element at the top of the stack.

1. When we push an element to the stack, we will push the element to the first stack and if the element is less than or equal to the top element of the second stack, we will push the element to the second stack as well.
2. When we pop an element from the stack, we will pop the element from the first stack and if the element is equal to the top element of the second stack, we will pop the element from the second stack as well (maintaining the count of the element).
3. When we get the top element of the stack, we will return the top element of the first stack.
4. When we get the minimum element of the stack, we will return the top element of the second stack.

Implementation

Here is a Java implementation of the above approach:

class MinStack {
    private record Tuple(int val, int count) {
    }

    private final Stack<Integer> stack;
    private final Stack<Tuple> minStack;

    public MinStack() {
        stack =  new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);

        if (minStack.isEmpty() || minStack.peek().val > val) {
            minStack.push(new Tuple(val, 1));
        } else if (minStack.peek().val == val) {
            Tuple top = minStack.pop();
            minStack.push(new Tuple(val, top.count + 1));
        }
    }

    public void pop() {
        if (minStack.peek().val == stack.peek()) {
            Tuple top = minStack.pop();
            if (top.count > 1) {
                minStack.push(new Tuple(top.val, top.count - 1));
            }
        }
        stack.pop();
    }

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

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

Complexity Analysis

The time complexity for all the operations is $O(1)$. The space complexity is $O(2 \cdot n) \approx O(N)$ where $N$ is the number of elements in the stack.