⌨️Java CodingIntermediate

Design a Min Stack (getMin in O(1))

📌 Definition:

Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1).

📖 Detailed Explanation:

Alongside the main stack, keep an auxiliary stack that stores the running minimum: on each push, push min(x, currentMin); on pop, pop both. The top of the min-stack is always the current minimum, so getMin is O(1). O(n) extra space in the simple form.

💻 Solutions:

static class MinStack {
    Deque<Integer> stack = new ArrayDeque<>(), mins = new ArrayDeque<>();
    void push(int x) {
        stack.push(x);
        mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
    }
    void pop() { stack.pop(); mins.pop(); }
    int top() { return stack.peek(); }
    int getMin() { return mins.peek(); }
}

class MinStack {
  constructor() { this.stack = []; this.mins = []; }
  push(x) {
    this.stack.push(x);
    this.mins.push(this.mins.length ? Math.min(x, this.getMin()) : x);
  }
  pop() { this.stack.pop(); this.mins.pop(); }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []

    def push(self, x):
        self.stack.append(x)
        self.mins.append(min(x, self.mins[-1]) if self.mins else x)

    def pop(self):
        self.stack.pop()
        self.mins.pop()

    def top(self):
        return self.stack[-1]

    def get_min(self):
        return self.mins[-1]

🔑 Key Points:

Auxiliary stack tracks the running minimum
Push min(x, prevMin); pop both together
getMin reads the min-stack top — O(1)
All operations O(1)

🌍 Real-World Example:

Tracking a running extreme in O(1) is useful for monitoring windows and undo stacks that must report the current best/worst instantly.

🎯 Scenario-Based Interview Question:

A candidate scans the whole stack on each getMin call. Why is that unacceptable, and what is the fix?