Min Stack

medium stack design

Problem

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(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.

Inputpush 3, push 5, push 2, getMin, pop, getMin

Output2, then 3

Min tracks the running minimum as values come and go.

operations (e.g. "push 3; push 5; push 2; pop; getMin")

class MinStack:
    def __init__(self):
        self.data = []
        self.mins = []
    def push(self, x):
        self.data.append(x)
        m = self.mins[-1] if self.mins else x
        self.mins.append(min(m, x))
    def pop(self):
        self.data.pop()
        self.mins.pop()
    def top(self):
        return self.data[-1]
    def getMin(self):
        return self.mins[-1]

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

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

class MinStack {
    vector<int> data, mins;
public:
    void push(int x) {
        data.push_back(x);
        mins.push_back(mins.empty() ? x : min(mins.back(), x));
    }
    void pop() { data.pop_back(); mins.pop_back(); }
    int top() { return data.back(); }
    int getMin() { return mins.back(); }
};

Explanation

The challenge is getting the minimum in constant time even as values are pushed and popped. The fix is to keep a second, parallel stack mins that stores the running minimum at every level of the main stack data.

Whenever you push x, you also push min(x, current top of mins) onto mins. So the top of mins is always the smallest value among everything currently in the stack. getMin just reads that top — no scanning required.

When you pop, you pop from both stacks together. That instantly restores the correct minimum for the smaller stack, because mins remembered the minimum at each earlier level.

Example: push 5 (min 5), push 2 (min 2), push 7 (min still 2), push 1 (min 1). getMin is 1. After two pops we are back to [5,2], and getMin reads 2.

It works because each level of mins snapshots the minimum at that moment, so removing the top automatically reveals the minimum that was valid before — every operation stays O(1).

Time: O(1) per op Space: O(n)