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.