Min Stack

Design a stack with constant-time top, pop, and minimum retrieval, and amortized constant-time push using Go slices.

Why this is worth learning

The minimum is part of each prefix state. Recording the prefix minimum alongside every pushed value makes popping a duplicate minimum unambiguous.

Before coding: one-minute experiment

After Push(2), Push(1), Push(1), Pop(), what must GetMin return?

Function signature

type MinStack struct { /* fields */ }

func Constructor() MinStack
func (s *MinStack) Push(val int)
func (s *MinStack) Pop()
func (s *MinStack) Top() int
func (s *MinStack) GetMin() int

Inputs / outputs

• Push(val): push a value.
• Pop(): remove the top value.
• Top(): return the top value.
• GetMin(): return the minimum value in the stack.

Example

Push(3), Push(1), Push(2)
GetMin() -> 1
Pop()
GetMin() -> 1

Constraints

• Up to 100_000 operations.
• Top and GetMin are called only on a nonempty stack. Pop on an empty stack does nothing.
• Pushed values may be any value representable by the course's 64-bit Go int.

Core idea (near-solution)

Maintain a second stack that tracks the minimum at each depth.

Invariant: minStack[i] is the minimum of stack[0..i].

Algorithm (step-by-step)

1. On Push, push val to the main stack and min(val, currentMin) to the min stack.
2. On Pop, pop both stacks.
3. Top returns main stack top.
4. GetMin returns min stack top.

Correctness sketch

Maintain equal-length value and minimum stacks, with mins[i] equal to the minimum of values[:i+1]. On push, append the new value and the smaller of it and the previous prefix minimum; this proves the invariant for the extended prefix. On pop, remove one element from each stack, restoring the already-correct metadata for the shorter prefix. Top reads the final value, and GetMin reads the final prefix minimum. Storing a minimum at every depth naturally preserves repeated minima: removing one occurrence reveals the correct minimum at the previous depth.

Trace (hand walkthrough)

Example input:
Push(3), Push(1), Push(2)
GetMin() -> 1
Pop()
GetMin() -> 1

Walk:
- Push 3 -> stack [3], min [3]
- Push 1 -> stack [3,1], min [3,1]
- Push 2 -> stack [3,1,2], min [3,1,1]
- GetMin=1; Pop removes 2; GetMin still 1

Pitfalls to avoid

• Forgetting to pop from the min stack when popping the main stack.
• Treating equal minima as one uncounted record. Each retained minimum occurrence needs a matching lifetime.

Debugging lens

Test duplicate minima, increasing and decreasing sequences, and returning to an empty stack before reuse. Top and GetMin require a nonempty stack; the existing Pop on empty is a no-op.

Complexity

Top, GetMin, and Pop perform O(1) work. Push is O(1) amortized with Go slice growth, rather than a worst-case no-allocation guarantee. Total auxiliary storage is O(n) for n retained values.

Implementation notes (Go)

• Use a slice of structs {val, min} or two parallel slices.
• Avoid calling Top or GetMin on an empty stack.

Contract precision

Call Top and GetMin only on a nonempty stack. The supplied Pop method intentionally does nothing on an empty stack. Constructor creates independent stacks for independent instances.

Reconstruction checkpoint

After Push(2), Push(1), Push(1), Pop(), what must GetMin return?

Return to Stack + Monotonic · Module quiz