Min Stack

Learning goal: Understand why an ordinary stack needs extra state to answer minimum queries in constant time.

Core idea A normal stack gives constant-time access to its top, but the minimum may be buried anywhere below it. If getMin() scans every stored value, one query costs O(n). The goal is to remember enough information during each push() so that the current minimum is always immediately available.

Algorithm plan

• Store values in a main stack.
• Store the minimum-so-far at the same depth in a second stack.
• On push(val), compare val with the previous minimum and push the smaller value onto the minimum stack.
• On pop(), remove one item from both stacks.
• On top() or getMin(), read the top of the relevant stack.

Micro-example After pushing -2, 0, and -3, the main stack is [-2, 0, -3]. The minimum stack is [-2, -2, -3], so getMin() reads -3 directly.

Pitfalls

• Do not scan the main stack inside getMin().
• Pop from both stacks together so their depths remain aligned.
• The minimum stack stores history, not just the single minimum value.

Recap

• The required operations must all be O(1).
• A parallel stack turns minimum lookup into a top operation.
• Each stack position has a matching minimum-so-far position.

Learning goal: See how each entry in the auxiliary stack represents the minimum of a complete prefix of the main stack.

Core idea At depth i, the minimum stack stores the smallest value among the first i + 1 values in the main stack. When a new value arrives, the new minimum is either that value or the previous minimum. This is the same information a scan would compute, but it is computed once during push() and reused by every later getMin().

Data structure model

For the main stack [-2, 0, -3], the parallel stack is [-2, -2, -3]. Notice that the second -2 is intentionally repeated: it preserves the minimum after 0 is later removed.

Micro-example Before pushing 4, suppose the previous minimum is 2. The new minimum is min(4, 2) = 2, so both stacks receive a corresponding entry.

Pitfalls

• Storing only a new record minimum loses information when that minimum is popped.
• Forgetting repeated minima breaks restoration after a pop.
• The two stacks must have equal lengths after every completed operation.

Recap

• Each auxiliary entry answers a prefix minimum.
• The new entry is min(new value, previous minimum).
• Repeated values are useful and sometimes necessary.

Learning goal: Translate the idea into precise operations and preserve the stack invariant.

Core idea The implementation uses two synchronized stacks: values and mins. For the first value, the minimum is the value itself. For every later push, compare against mins[-1]. Because pop() removes the newest value, removing the matching minimum entry automatically restores the minimum that was valid one level earlier.

Data structure model

Micro-example Push -2: mins = [-2]. Push 0: mins = [-2, -2]; push -3: mins = [-2, -2, -3].

Pitfalls

• Calling min() over all of values inside getMin() defeats the design.
• Popping only values leaves stale minimum data.
• Empty-stack handling should follow the stated method preconditions.

Recap

• Synchronization preserves the prefix-minimum invariant.
• Every operation touches only stack tops.
• The minimum is available in O(1) time.

Learning goal: Trace one complete sequence and observe both stacks change together.

Core idea We will use the sequence push(-2), push(0), push(-3), getMin(), pop(), getMin(), top(), pop(), getMin(). Each push creates a pair: the actual value and the minimum valid through that depth. Each pop removes the pair, which exposes the earlier minimum without recomputation.

Algorithm plan

• Start with both stacks empty.
• Process each operation from left to right.
• For push, append a value/minimum pair.
• For getMin, inspect the minimum component of the top pair.
• For pop, remove the top pair.

Micro-example After three pushes, the pairs are (-2, -2), (0, -2), (-3, -3). After popping -3, the pair (0, -2) becomes visible, so the minimum immediately returns to -2.

Pitfalls

• Track the minimum after each push, not only when a new record minimum appears.
• A getMin() does not modify either stack.
• The final minimum after removing 0 is still -2, not an empty result.

Recap

• The trace follows the problem example exactly.
• The minimum changes on pushes and is restored by paired pops.
• Queries are reads, not scans or mutations.

Learning goal: Identify the implementation mistakes that break either correctness or the required complexity.

Core idea The auxiliary stack is valuable only if it is updated exactly when the main stack changes. The most common wrong approach is to call a minimum function that scans every element during getMin(). That produces the right answer, but it violates the central performance requirement.

Algorithm plan

• For every push, append one value and one minimum-so-far entry.
• For every pop, remove one entry from each stack.
• For getMin, return only the auxiliary stack's top.
• Test a decreasing sequence, an increasing sequence, and duplicate minima.

Micro-example For push(2), push(2), pop(), the minimum must still be 2. The minimum stack should be [2, 2], not merely [2], so one pop does not erase the remaining minimum.

Pitfalls

• Do not store only record-breaking minima; duplicates must be represented.
• Do not let the two stacks drift to different lengths.
• Do not confuse top() with getMin() when the top value is not the smallest.
• Check negative values and repeated minimum values.

Recap

• Correctness depends on synchronized push/pop operations.
• Duplicate minima need duplicate auxiliary entries.
• The scan-based solution is explicitly too slow for getMin().

Learning goal: Justify the final complexity and recognize the reusable design pattern.

Core idea Each operation performs a constant number of stack actions and comparisons. The auxiliary stack stores one minimum entry per main-stack entry, so the extra memory grows linearly with the number of stored values. This trades O(n) space for O(1) minimum queries.

Data structure model

Micro-example With n values, both stacks contain at most n entries. Even after many getMin() calls, no additional scan is performed.

Pitfalls

• Do not report O(1) space: the minimum stack grows with n.
• Do not claim only getMin() is constant time; all four operations are.
• Do not replace the auxiliary history with one global minimum unless you also track restoration information.

Recap

• Time is O(1) per operation.
• Space is O(n).
• The parallel stack converts a global-looking query into a local read.