Min Stack

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.

class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        // only push the old minimum value when the current 
        // minimum value changes after pushing the new value x
        if(x <= min){          
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }

    public void pop() {
        // if pop operation could result in the changing of the current minimum value, 
        // pop twice and change the current minimum value to the last minimum value.
        if(stack.pop() == min) min=stack.pop();
    }

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

    public int getMin() {
        return min;
    }
}

The Min Stack problem involves designing a stack data structure that supports standard stack operations (push, pop, top) and can also return the minimum element in constant time. One less efficient but still acceptable approach is to use two stacks: one to store the actual values and another to track the minimum values. When pushing a new value, you compare it with the current minimum (top of the min stack) and push the new minimum onto the min stack. When popping, you also pop from the min stack to keep both stacks synchronized.

Another approach is to store tuples on the stack where each tuple contains the value and the minimum value at the time of pushing. For example, when you push a value, you push (value, min(current_min, new_value)). This ensures that each element in the stack carries the minimum up to that point. The key idea in both approaches is maintaining an auxiliary structure that keeps track of the minimum value efficiently, ensuring that operations like push and pop do not degrade in performance. The actual optimal solution, listed above, is to share a single stack for both values and minimums but only push or pop the minimum when needed. This is somewhat gross from a software engineering point of view, as the mixing of types of values on the stack could prove to be error prone with future refactorings of the code, but it uses the least amount of space. This problem teaches the importance of auxiliary data structures in optimizing standard operations.

Related Problems