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.

Practice

1. What is the main purpose of a Min Stack data structure?

easy

A. To store only the minimum elements pushed so far

B. To sort elements in ascending order automatically

C. To retrieve the minimum element in constant time along with stack operations

D. To reverse the order of elements pushed into the stack

Solution

1. Step 1: Understand the Min Stack concept

   A Min Stack is designed to support normal stack operations and also return the minimum element quickly.

2. Step 2: Identify the key feature

   The key feature is retrieving the minimum element in constant time, not sorting or reversing.

3. Final Answer:

   To retrieve the minimum element in constant time along with stack operations -> Option C

4. Quick Check:

   Min Stack = fast minimum retrieval [OK]

Hint: Min Stack always tracks minimum for O(1) retrieval [OK]

Common Mistakes:

• Thinking Min Stack sorts elements
• Assuming it stores only minimum elements
• Confusing with reversing stack order

2. Which of the following is the correct way to initialize a Min Stack class in Python?

easy

A. class MinStack:
def __init__(self):
stack = []
min_stack = []

B. class MinStack:
def __init__(self):
self = []

C. class MinStack:
def __init__(self):
self.stack = None
self.min_stack = None

D. class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []

Solution

1. Step 1: Check correct attribute initialization

   Attributes must be initialized with self to be instance variables.

2. Step 2: Verify list initialization

   Both stack and min_stack should be empty lists initialized with self.

3. Final Answer:

   class MinStack:\n def __init__(self):\n self.stack = []\n self.min_stack = [] -> Option D

4. Quick Check:

   Use self for instance variables [OK]

Hint: Always use self to define instance variables in __init__ [OK]

Common Mistakes:

• Not using self for attributes
• Initializing attributes as None instead of lists
• Assigning self to a list directly

3. What will be the output of the following code snippet?

min_stack = MinStack()
min_stack.push(3)
min_stack.push(5)
min_stack.push(2)
min_stack.push(1)
min_stack.pop()
print(min_stack.get_min())

medium

A. 2

B. 1

C. 3

D. 5

Solution

1. Step 1: Trace push operations and min tracking

   Push 3 (min=3), push 5 (min=3), push 2 (min=2), push 1 (min=1).

2. Step 2: Pop removes 1, min updates to 2

   After popping 1, the minimum is the next smallest, which is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Pop removes min 1, next min = 2 [OK]

Hint: Pop min, next min is previous min in min stack [OK]

Common Mistakes:

• Assuming min stays 1 after pop
• Confusing push order with min updates
• Ignoring min stack updates on pop

4. Identify the bug in this Min Stack pop method and choose the correct fix:

def pop(self):
    if self.stack:
        self.stack.pop()
        self.min_stack.pop()

medium

A. No bug; code is correct

B. Pop from min_stack only if popped element equals current min

C. Pop from min_stack before popping from stack

D. Check if min_stack is empty before popping it

Solution

1. Step 1: Understand pop logic in Min Stack

   Pop from min_stack only if the popped element is the current minimum to keep min_stack accurate.

2. Step 2: Identify bug and fix

   Current code always pops min_stack, which can cause errors if min_stack is out of sync.

3. Final Answer:

   Pop from min_stack only if popped element equals current min -> Option B

4. Quick Check:

   Pop min_stack conditionally to keep min correct [OK]

Hint: Pop min_stack only if popped value equals current min [OK]

Common Mistakes:

• Always popping min_stack without condition
• Not checking min_stack emptiness
• Changing pop order incorrectly

5. You want to design a Min Stack that supports push, pop, top, and get_min all in O(1) time. Which approach is best?

hard

A. Use two stacks: one for all elements, one for current minimums

B. Use a queue to store elements and a variable for min

C. Use one stack and scan all elements to find min on get_min

D. Use a linked list and traverse to find min on each get_min

Solution

1. Step 1: Analyze time complexity requirements

   All operations must be O(1), so scanning or traversing is not allowed.

2. Step 2: Choose data structure approach

   Using two stacks, one for elements and one for minimums, allows constant time min retrieval.

3. Final Answer:

   Use two stacks: one for all elements, one for current minimums -> Option A

4. Quick Check:

   Two stacks = O(1) min retrieval [OK]

Hint: Two stacks track elements and minimums for O(1) min [OK]

Common Mistakes:

• Using scanning which is O(n)
• Using queue which doesn't support stack operations
• Using linked list traversal for min