🧭 Conceptual Foundation & Pattern Intuition

A plain stack answers top() at once but has to scan everything to find its minimum. One running variable, self.min, fixes push but breaks pop: when the smallest value leaves, the variable can't know the next smallest. The Min-Stack Trick uses the one fact that makes a stack special: it only ever changes at its top. While an entry sits on the stack, nothing below it changes, so the minimum of "this entry and everything below it" stays true until the entry itself is popped. Compute that minimum once, at push time, and store it in the entry as (val, current_min). The top entry then always holds the minimum of the whole stack, and pop needs no repair.

🥞 The Analogy: A Pile of Plates With a Note on Each

You pile up plates of different sizes, and someone keeps asking for the size of the smallest plate in the pile. Each time you put a plate down, you stick a note on it: "the smallest plate from here down is size X", copying the number from the note below if that one is smaller. To answer, you read the note on the top plate. When you lift a plate off, the note on the plate now on top was written when that plate was the top, and nothing under it has changed since, so it is still right.

🪄 The Mathematical Harmony / Magic Trick

if self.stack:
    current_min = min(val, self.stack[-1][1])
else:
    current_min = val
self.stack.append((val, current_min))
 

current_min is a running minimum from the bottom of the stack up to this entry, and it is stored with the entry, so every prefix of the stack keeps its own answer. Popping removes exactly one prefix, and the prefix below still has its answer on its own top entry. Compare val with the minimum carried below, self.stack[-1][1], not with the value below, self.stack[-1][0].

💡 Summary

Store the answer with each entry: (val, current_min), where current_min = min(val, self.stack[-1][1]). getMin reads the top pair, pop removes it, and nothing is ever recomputed. $O(1)$ per call, $O(N)$ space.