Min Stack Design in DSA Python - Execution Trace

Concept Flow - Min Stack Design

Push value

↓

Compare with current min

↓

If smaller or equal, push to min stack

↓

Push to main stack

↓

Pop value

↓

Check if popped value == min stack top

↓

If yes, pop min stack

↓

Get min

↓

Return top of min stack

This flow shows how each push compares with the current minimum and updates a min stack to track minimums, and how pop keeps both stacks in sync.

Execution Sample

DSA Python

stack = []
min_stack = []

def push(val):
    if not min_stack or val <= min_stack[-1]:
        min_stack.append(val)
    stack.append(val)

def pop():
    if stack:
        val = stack.pop()
        if val == min_stack[-1]:
            min_stack.pop()
        return val
    return None

def getMin():
    if min_stack:
        return min_stack[-1]
    return None

push(5)
push(3)
pop()

This code pushes 5 and 3 onto the stack, tracking minimums, then pops the top value.

Execution Table

Step	Operation	Main Stack	Min Stack	Pointer Changes	Visual State
1	push(5)	[5]	[5]	Push 5 to main and min stacks	Main: 5 -> null Min: 5 -> null
2	push(3)	[5, 3]	[5, 3]	3 <= min top(5), push 3 to min stack	Main: 5 -> 3 -> null Min: 5 -> 3 -> null
3	pop()	[5]	[5]	Pop 3 from main; 3 == min top, pop min stack	Main: 5 -> null Min: 5 -> null
4	getMin()	[5]	[5]	Return top of min stack: 5	Min is 5
5	pop()	[]	[]	Pop 5 from main; 5 == min top, pop min stack	Main: null Min: null
6	getMin()	[]	[]	Min stack empty, no min	Min is None

💡 Execution stops after all operations are performed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
main_stack	[]	[5]	[5, 3]	[5]	[5]	[]	[]
min_stack	[]	[5]	[5, 3]	[5]	[5]	[]	[]
min_value	None	5	3	5	5	None	None

Key Moments - 3 Insights

Why do we push the value to min stack only if it is smaller or equal to current min?

Because the min stack tracks the minimum values in order. When a new value is smaller or equal, it becomes the new minimum. This is shown in execution_table rows 1 and 2 where 5 and then 3 are pushed to min stack.

What happens to min stack when we pop a value that is the current minimum?

We pop the min stack as well to keep minimum tracking correct. See execution_table row 3 where popping 3 from main stack also pops 3 from min stack.

Why does getMin return the top of min stack?

Because min stack always holds the current minimum at its top. This is shown in execution_table row 4 where getMin returns 5 from min stack top.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the state of the min stack?

A [3]

B [5]

C [5, 3]

D []

💡 Hint

Check the 'Min Stack' column at step 2 in execution_table.

At which step does the min stack pop a value?

A Step 3

B Step 2

C Step 1

D Step 4

💡 Hint

Look for 'pop min stack' in Pointer Changes column in execution_table.

If we push a value larger than current min, what happens to min stack?

A Push the new value to min stack

B Do nothing to min stack

C Pop the min stack

D Clear the min stack

💡 Hint

Min stack only changes when new value <= current min, see concept_flow.

Concept Snapshot

Min Stack Design:
- Use two stacks: main and min stack
- Push: add to main stack; if value <= min top, push to min stack
- Pop: remove from main; if popped == min top, pop min stack
- getMin: return top of min stack
- Keeps track of minimum in O(1) time

Full Transcript

Min Stack Design uses two stacks to track values and minimums. When pushing, the value goes to main stack. If it is smaller or equal to current minimum, it also goes to min stack. When popping, if the popped value equals the min stack top, pop min stack too. getMin returns the top of min stack, which is the current minimum. This keeps minimum retrieval fast and accurate.

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