Augmented Stack

Foundations

In the first lesson, the stack held items waiting for a match, and only the top mattered. Now, what if you also need a fact about everything in the stack, such as its smallest value, after every push and every pop?

A running value such as the minimum is easy to update on a push: compare the new element with the old minimum. A pop is the problem, because the element leaving may be the minimum, and nothing says what the minimum was before it arrived without a rescan. The fix is a snapshot: store each element together with the answer for the stack up to and including it, so a pop restores the previous answer for free.

Push nums = [7, 1, 5, 3, 6] as pairs of value and minimum so far: (7, 7), (1, 1), (5, 1), (3, 1), (6, 1). The minimum is always the second field of the top pair, here 1. Pop three times, removing 6, 3, and 5, and the top pair (1, 1) still says 1; pop once more and (7, 7) says the minimum is 7 again, with no scan.

Case Scenario

Min Stack asks for exactly that: push, pop, top, and getMin, each in O(1). Each entry stores (val, low), where low is the minimum from the bottom of the stack up to that entry. After pushes of -2, 0, and -3, getMin() returns -3; after one pop, the top pair (0, -2) answers -2 without a scan.

The direct approach keeps a plain stack and scans it whenever getMin is called. push, pop, and top stay O(1), but getMin costs O(n) for n items, so a caller who asks after every push pays O(n²) overall. The scans also repeat themselves: the minimum of the lower entries never changes until a pop reaches them.