Min Stack Design in DSA Python

Mental Model

A Min Stack keeps track of the smallest value at every point so we can get the minimum quickly.

Analogy: Imagine a stack of plates where each plate has a note showing the smallest plate below it. When you add or remove plates, you update the note so you always know the smallest plate on top.

Stack top ↑
[7, min=3] -> [3, min=3] -> [5, min=5] -> null

Dry Run Walkthrough

Input: Push 5, Push 3, Push 7, GetMin, Pop, GetMin

Goal: Show how the stack updates and how minimum changes after each operation

Step 1: Push 5 onto stack

[5, min=5] -> null ↑

Why: First element, so min is 5

Step 2: Push 3 onto stack

[3, min=3] -> [5, min=5] -> null ↑

Why: 3 is smaller than previous min 5, update min to 3

Step 3: Push 7 onto stack

[7, min=3] -> [3, min=3] -> [5, min=5] -> null ↑

Why: 7 is bigger than min 3, min stays 3

Step 4: GetMin returns 3

[7, min=3] -> [3, min=3] -> [5, min=5] -> null ↑

Why: Top node min value is 3

Step 5: Pop top element (7)

[3, min=3] -> [5, min=5] -> null ↑

Why: Remove 7, min remains 3 from next node

Step 6: GetMin returns 3

[3, min=3] -> [5, min=5] -> null ↑

Why: Top node min value is still 3

Result:

[3, min=3] -> [5, min=5] -> null ↑
Minimum value is 3

Annotated Code

DSA Python

class MinStack:
    def __init__(self):
        self.stack = []  # Each element is a tuple (value, current_min)

    def push(self, val: int) -> None:
        current_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, current_min))  # Push value and min so far

    def pop(self) -> None:
        if self.stack:
            self.stack.pop()  # Remove top element

    def top(self) -> int:
        if self.stack:
            return self.stack[-1][0]  # Return top value
        return None

    def getMin(self) -> int:
        if self.stack:
            return self.stack[-1][1]  # Return current min
        return None

# Driver code to run the dry run example
min_stack = MinStack()
min_stack.push(5)
min_stack.push(3)
min_stack.push(7)
print(min_stack.getMin())  # Expected 3
min_stack.pop()
print(min_stack.getMin())  # Expected 3

current_min = val if not self.stack else min(val, self.stack[-1][1])

Calculate new min by comparing pushed value with current min

self.stack.append((val, current_min))

Store value and min so far together

self.stack.pop()

Remove top element, min updates automatically

return self.stack[-1][1]

Get current min from top element

Output

3

3

Complexity Analysis

Time: O(1) for push, pop, top, and getMin because all operations use the top element only

Space: O(n) because we store each element with its min value

vs Alternative: Compared to scanning the whole stack for min (O(n)), this design keeps min retrieval fast at O(1)

Edge Cases

Empty stack when calling pop or getMin

Returns None safely without error

DSA Python

if self.stack:

Push duplicate minimum values

Min stack correctly tracks min even with duplicates

DSA Python

current_min = val if not self.stack else min(val, self.stack[-1][1])

Pop until stack is empty

Stack becomes empty and getMin returns None

DSA Python

if self.stack:

When to Use This Pattern

When a problem asks for retrieving the minimum value in a stack quickly, use the Min Stack pattern to keep track of minimums during push and pop operations.

Common Mistakes

Mistake: Only storing values without tracking minimums, causing getMin to be slow
Fix: Store each pushed value along with the minimum value so far

Mistake: Updating min incorrectly when pushing new values
Fix: Always compare new value with current min and store the smaller one

Summary

Keeps track of the minimum value in a stack at all times.

Use when you need to get the minimum value quickly while pushing and popping.

Store each element with the minimum value so far to get O(1) min retrieval.