Min Stack medium

Problem Statement

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

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example 1

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output: [null,null,null,null,-3,null,0,-2]

Explanation:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Example 2

Input: ["MinStack","push","getMin","pop","getMin"]
[[],[-2],[],[],[]]

Output: [null,null,-2,null,-2]

Explanation:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.getMin(); // return -2
minStack.pop();
minStack.getMin(); // return -2

Steps

To achieve constant time complexity for getMin(), we need an auxiliary data structure to track the minimum element efficiently. We'll use a second stack to store the minimum values encountered so far.

1. Data Structures: We'll use two stacks:

   • stack: A regular stack to store the elements.
   • minStack: A stack to store the minimum values encountered at each push operation.

2. push(x): Push x onto stack. If minStack is empty or x is less than or equal to the top of minStack, push x onto minStack as well. This ensures minStack always has the minimum element seen so far at its top.

3. pop(): Pop from stack. If the popped element is equal to the top of minStack, pop from minStack as well to maintain consistency.

4. top(): Return the top element of stack.

5. getMin(): Return the top element of minStack.

Explanation

The key is the minStack. It mirrors the stack but only keeps track of minimum values. Whenever a new minimum is encountered, it's added to minStack. When a minimum element is popped from stack, the corresponding minimum is also popped from minStack. This ensures minStack always has the current minimum at the top.

Code

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

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

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        if (stack.isEmpty()) return; //Handle empty stack case

        int popped = stack.pop();
        if (popped == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        if(stack.isEmpty()) throw new EmptyStackException(); //Handle empty stack case
        return stack.peek();
    }

    public int getMin() {
        if (minStack.isEmpty()) throw new EmptyStackException(); //Handle empty stack case
        return minStack.peek();
    }
}

class EmptyStackException extends RuntimeException{
    public EmptyStackException(){}
    public EmptyStackException(String s){
        super(s);
    }
}

Complexity

• Time Complexity:

  • push(x), pop(), top(), getMin(): O(1) All operations are constant time because they involve only stack operations (push, pop, peek).

• Space Complexity: O(N), where N is the number of elements in the stack. We are using two stacks, each potentially storing up to N elements in the worst case.