• -2³¹ <= val <= 2³¹ - 1
• pop, top and getMin are always called on a non-empty stack
• At most 3 × 10⁴ calls will be made to push, pop, top, and getMin

A stack is a pile you touch only from the top: push adds on top, pop removes the top, top peeks at it — all instant, O(1). The twist here is a fourth request, getMin, which must return the smallest value anywhere in the stack, also in O(1). That's the tension: a stack only ever exposes its top, but the minimum could be buried at the very bottom.

Keep an ordinary stack and, when getMin is asked, scan all the stored values for the smallest. Correct, but scanning N elements is O(N) per call — and with up to 3 × 10⁴ calls that's quadratic overall. The waste is obvious once named: we recompute the minimum from scratch every single time, even though the stack barely changed since the last call. Whenever you catch yourself recomputing an answer that only shifts a little between calls, the fix is usually to remember it instead.

Here's the fact that unlocks O(1). A stack only changes at the top — you can't touch the middle. So consider the moment any value x is pushed: the minimum of everything at or below it is fixed forever, because nothing beneath x can change until x itself is popped. In other words, each depth of the stack has its own permanent minimum: the min of the whole stack when the stack was that tall. If we could store, next to each element, "the minimum of everything from here down," then getMin is just reading that number off the top.

Keep a second stack, min_stack, that rises and falls in lockstep with the main one. Its top always holds the minimum of the current main stack. On push(x), the new overall minimum is simply x compared against the previous minimum (the current min_stack top) — push the smaller of the two. On pop, remove the top of both stacks together, so min_stack's top automatically falls back to the minimum that was true one level down. getMin reads min_stack's top. Everything is O(1).

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []      # min_stack[i] = min of stack[0..i]

    def push(self, val):
        self.stack.append(val)
        cur_min = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(cur_min)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()     # keep the two perfectly in sync

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

    def getMin(self):
        return self.min_stack[-1]

The duplicate-minimum case is the one that trips naive fixes: push 0, then 0 again. min_stack holds [0, 0], so after popping one 0 the min is still 0 — correct, because a second copy of the minimum is still in the stack. Storing the min per level handles this for free; a single "remember one min value" variable would wrongly forget it.

You bought O(1) on all four operations by spending O(N) extra space on the parallel stack — the familiar trade memory for speed. The reusable idea is broader than the minimum: when a stack must also report some running aggregate — min, max, sum, count — carry that aggregate in a parallel stack that pushes and pops in lockstep. Each level snapshots the aggregate of everything beneath it, so it self-restores on pop. That single pattern answers a whole family of "stack that also tracks X" interview questions.