Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time.

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.

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

• Invariant: minStack[i] is the minimum of stack[0..i].
• Each push records the minimum up to that depth.
• Popping both stacks keeps values and minima aligned.
• The top of the min stack is always the correct minimum.

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.
• Handling empty stack operations (assume valid operations if not specified otherwise).

Complexity

• Time: O(1) per operation.
• Extra space: O(n).

Implementation notes (Go)

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