how a min stack keeps getMin O(1)

i was solving min stack on neetcode — a stack where getMin() also has to be O(1).

my first attempt kept one curr_min on the instance and updated it on every push. it looks right until something pops:

push(5)   # curr_min = 5
push(2)   # curr_min = 2
pop()     # curr_min is still 2 — but 2 is gone, the answer is 5

the variable has nowhere to remember 5. i had treated the minimum as one global value, when it is really a different value at every depth of the stack.

so store it at that depth. each entry holds a tuple of the value and the minimum as of that entry:

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

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

push only ever looks at the top, because the top already carries the answer for everything beneath it:

push(5)   # (5, 5)
push(2)   # (2, 2)   min(5, 2)
push(7)   # (7, 2)   min(2, 7)
pop()     # top is (2, 2) again → getMin() == 2
pop()     # top is (5, 5) again → getMin() == 5

the part worth keeping: all the minimum logic lives in push. pop has none — it removes the top tuple and nothing else. it does not need any, because the minimum was stored inside the tuple it just removed, and the tuple underneath is already carrying the correct earlier minimum.

every operation is O(1), and each entry stores one extra int, so space is still O(n).