155. Min Stack | LeetCode | Top Interview 150 | Coding Questions

Source: Dev.to

Problem

Min Stack – LeetCode

Solution Overview

The goal is to implement a stack that, in addition to the usual push, pop, and top operations, can return the minimum element in O(1) time.
The typical approach uses two stacks:

• stack – stores all pushed values.
• minStack – stores the current minimum values.
  When a new value is pushed, it is also pushed onto minStack if it is ≤ the current minimum.
  When popping, if the popped value equals the top of minStack, we also pop from minStack.

This ensures that the top of minStack always holds the minimum element of the main stack.

Implementation (Java)

class MinStack {

    private Stack stack;
    private Stack minStack;

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

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

    public void pop() {
        int poppedVal = stack.pop();
        if (poppedVal == minStack.peek()) {
            minStack.pop();
        }
    }

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

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

/*
 * Usage example:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int topVal = obj.top();
 * int minVal = obj.getMin();
 */