Min Stack

Approach Summary

Maintain two stacks: main stack and min stack. Push to min stack only when new value <= current minimum.

Full Solution & Approach

The trick is to answer getMin in O(1) without scanning the whole stack. Maintain a second stack, mins, that tracks the running minimum. On push(val): push val onto the main stack, and onto mins push min(val, current top of mins). Because mins stores the minimum at every prefix of the stack, its top is always the global minimum. On pop: pop both stacks in sync. top returns the main stack's top and getMin returns mins' top. The two stacks always have equal length, so they never desynchronize. Alternative formulations push (value, min_so_far) pairs onto a single stack, or push a sentinel whenever a new minimum arrives — the parallel-stack version is the most readable and equally valid.

Every operation does constant work — a push or pop plus an O(1) min comparison — so all four methods are O(1). Space is O(n) for the two stacks, bounded by the number of pushed values.

Solution Code

Solution

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        self.mins.append(val if not self.mins else min(val, self.mins[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.mins.pop()

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

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

class MinStack {
  constructor() {
    this.stack = [];
    this.mins = [];
  }
  push(val) {
    this.stack.push(val);
    this.mins.push(this.mins.length ? Math.min(val, this.mins[this.mins.length - 1]) : val);
  }
  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 {
    private Deque<Integer> stack = new ArrayDeque<>();
    private Deque<Integer> mins = new ArrayDeque<>();

    public void push(int val) {
        stack.push(val);
        mins.push(mins.isEmpty() ? val : Math.min(val, mins.peek()));
    }

    public void pop() {
        stack.pop();
        mins.pop();
    }

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

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

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

Edge Cases to Watch

Repeated minimum values — mins must store duplicates, e.g. push 5, 3, 3 keeps [5, 3, 3]
Push after pop — mins stays in sync because both stacks are popped together
getMin on a fresh stack — the problem guarantees no top/getMin on an empty stack

How to Recognize This Pattern

Stack with O(1) minimum retrieval

Complexity Analysis

Time Complexity

O(1) all ops

Space Complexity

O(n)