Min Stack

• Difficulty: Medium
• Topics: Stack, Design
• Link: https://leetcode.com/problems/min-stack/

Problem Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

• -231 <= val <= 231 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement
We require a LIFO data structure supporting four operations with $O(1)$ time complexity:

• Initialization: Construct empty stack
• Push(val): Insert element val onto stack top
• Pop(): Remove top element (always called on non-empty stack)
• Top(): Retrieve top element without removal
• getMin(): Retrieve minimum element in current stack

The critical constraint is maintaining minimum knowledge despite stack mutations, precluding naive $O(n)$ scans.

Beginner Explanation
Imagine stacking plates where you must always know the lightest plate currently stacked. You can:

• Add plates (push)
• Remove the top plate (pop)
• Check the top plate (top)
• Instantly know the lightest plate (getMin)

The challenge is tracking the lightest plate efficiently despite adding/removing plates.

Mathematical Formulation
Let $S = [s_0, s_1, ..., s_{n-1}]$ represent stack state ($s_0$ = bottom, $s_{n-1}$ = top). Define:

• $push(v): S \rightarrow S \cup \{v\}$ where $v$ becomes new $s_n$
• $pop(): S \rightarrow S \setminus \{s_{n-1}\}$
• $top(): \text{returns } s_{n-1}$
• $getMin(): \text{returns } \min(S)$

We require all four operations execute in $O(1)$ time regardless of $|S|$.

Constraint Analysis

• $-2^{31} \leq val \leq 2^{31}-1$: Integer range implies potential overflow concerns (though not directly in Python), and negative values must be handled
• Non-empty stack for pop/top/getMin: Eliminates null-checking overhead in these operations
• $3 \times 10^4$ calls: Upper bound permits $O(n)$ space solutions but demands $O(1)$ time per operation
• Hidden edge cases:
  • Repeated minimum values (multiple identical mins)
  • Minimum at bottom then removed
  • Alternating push/pop patterns that change minimum frequently
  • Single-element corner cases

---

2. Intuition Scaffolding

Real-World Metaphor
Consider a warehouse stacking crates where management needs instant knowledge of the lightest crate currently stored. Workers could attach a “current minimum” tag to each crate showing the lightest crate from that point downward. When adding a new crate, compare its weight to the previous top’s minimum tag.

Gaming Analogy
In RPG inventory management, your backpack has limited space (stack). Each item has weight, and you need to know the lightest item for encumbrance calculations. You could maintain a separate “lightest item” registry that updates when adding/removing items.

Math Analogy
Consider a sequence $a_1, a_2, ..., a_n$ where we need the prefix minimum $m_i = \min(a_1, ..., a_i)$ after each operation. The challenge is maintaining $m_n$ when the sequence length changes via append/remove-last operations.

Common Pitfalls

1. Single min variable: Fails when current min is popped
2. Sorted structure: Breaks $O(1)$ requirement
3. Recalculating on getMin: $O(n)$ time violation
4. Storing only deltas: Complex overflow handling
5. Separate min stack without coordination: Gets out of sync with main stack

---

3. Approach Encyclopedia

Brute Force Approach

class MinStack:
    def __init__(self):
        self.stack = []
    
    def push(self, val: int) -> None:
        self.stack.append(val)
    
    def pop(self) -> None:
        self.stack.pop()
    
    def top(self) -> int:
        return self.stack[-1]
    
    def getMin(self) -> int:
        return min(self.stack)  # O(n) scan - violates requirements

Complexity: Push $O(1)$, Pop $O(1)$, Top $O(1)$, GetMin $O(n)$
Space: $O(n)$

Optimized Two-Stack Approach
Maintain parallel stacks: one for values, one for current minimums.

Operation        Main Stack    Min Stack
push(3)         [3]           [3]
push(1)         [3,1]         [3,1]  
push(2)         [3,1,2]       [3,1,1]
push(0)         [3,1,2,0]     [3,1,1,0]
pop()           [3,1,2]       [3,1,1]
getMin() → 1

Mathematical Complexity:

• Time: All operations $O(1)$ since stack operations are $O(1)$
• Space: $O(2n) = O(n)$ worst-case (min stack duplicates main stack for descending sequence)

Optimized Single-Stack Approach
Store tuples (value, current_min) in single stack:

push(3): [(3,3)]
push(1): [(3,3), (1,1)]
push(2): [(3,3), (1,1), (2,1)]
push(0): [(3,3), (1,1), (2,1), (0,0)]

---

4. Code Deep Dive

Optimal Solution (Two-Stack)

class MinStack:
    def __init__(self):
        self.stack = []       # Main value storage
        self.min_stack = []   # Parallel min tracking
    
    def push(self, val: int) -> None:
        # Always push to main stack
        self.stack.append(val)
        
        # Update min_stack: push current min (either new val or existing min)
        if not self.min_stack:
            self.min_stack.append(val)
        else:
            self.min_stack.append(min(val, self.min_stack[-1]))
    
    def pop(self) -> None:
        # Synchronized removal from both stacks
        self.stack.pop()
        self.min_stack.pop()
    
    def top(self) -> int:
        return self.stack[-1]  # Direct access to top element
    
    def getMin(self) -> int:
        return self.min_stack[-1]  # Current min always at min_stack top

Line-by-Line Analysis

• Lines 2-5: Dual stack initialization ensures clean separation of concerns
• Lines 9-13: Min stack update logic handles both empty and non-empty cases
• Lines 15-17: Synchronized popping maintains stack consistency
• Lines 19-20: Direct indexing provides $O(1)$ access
• Lines 22-23: Min retrieval leverages pre-computed minimums

Edge Case Handling

• Empty initialization: Both stacks empty, handled naturally
• Single element: Min stack correctly tracks single value
• Duplicate minimums: Min stack stores duplicates, preserving correctness after pop
• Alternating values: min(val, self.min_stack[-1]) ensures proper tracking

---

5. Complexity War Room

Hardware-Aware Analysis
At constraint maximum (30,000 operations):

• Memory: ~30,000 × 8 bytes × 2 stacks ≈ 480KB (fits comfortably in L2/L3 cache)
• Operations: ~120,000 total operations at nanosecond scale = sub-millisecond runtime

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(1)/O(n)	O(n)	10/10	❌ Fails requirements
Two-Stack	O(1)	O(n)	9/10	✅ Clear and efficient
Single-Stack Tuples	O(1)	O(n)	8/10	✅ Slightly less obvious
Linked List + Min	O(1)	O(n)	6/10	⚠️ Overly complex

---

6. Pro Mode Extras

Algorithm Variants

1. Space-Optimized MinStack: Only push to min_stack when new min ≤ current min
2. Thread-Safe MinStack: Add locking mechanisms for concurrent access
3. Persistent MinStack: Support versioning for undo/redo functionality
4. Multi-MinStack: Track both min and max simultaneously

Interview Cheat Sheet

• First Mention: Always state time/space complexity upfront
• Whiteboard: Draw parallel stack visualization immediately
• Edge Cases: Explicitly discuss duplicate values and single-element scenarios
• Trade-offs: Acknowledge space vs time trade-off (2n vs n space)
• Testing: Walk through provided example step-by-step

Mathematical Extension
For space-optimized version, the amortized cost remains $O(1)$ with space complexity improving to $O(n)$ worst-case but $O(1)$ best-case (constant values). The number of min-stack pushes follows a geometric distribution when values are randomly ordered.