Min Stack Design in DSA C - Execution Trace

Concept Flow - Min Stack Design

Push x

↓

Push x to main stack

↓

Is min stack empty or x <= top of min stack?

No→Do nothing

Yes↓

Push x to min stack

↓

Done

↓

Pop

↓

Pop from main stack

↓

Is popped value == top of min stack?

No→Do nothing

Yes↓

Pop from min stack

↓

Done

↓

GetMin

↓

Return top of min stack

Push adds to main stack and min stack if needed; Pop removes from both if top matches; GetMin returns min stack top.

Execution Sample

DSA C

push(5)
push(3)
push(7)
pop()
getMin()

Push values 5, 3, 7; pop top; get minimum value in stack.

Execution Table

Step	Operation	Main Stack	Min Stack	Pointer Changes	Visual State
1	push(5)	5	5	main_top=0, min_top=0	Main: 5 -> null; Min: 5 -> null
2	push(3)	5 -> 3	5 -> 3	main_top=1, min_top=1	Main: 5 -> 3 -> null; Min: 5 -> 3 -> null
3	push(7)	5 -> 3 -> 7	5 -> 3	main_top=2, min_top=1	Main: 5 -> 3 -> 7 -> null; Min: 5 -> 3 -> null
4	pop()	5 -> 3	5 -> 3	main_top=1, min_top=1	Main: 5 -> 3 -> null; Min: 5 -> 3 -> null
5	getMin()	5 -> 3	5 -> 3	No change	Min top is 3

💡 Execution stops after getMin returns current minimum 3.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
main_stack	empty	[5]	[5,3]	[5,3,7]	[5,3]	[5,3]
min_stack	empty	[5]	[5,3]	[5,3]	[5,3]	[5,3]
main_top	-1	0	1	2	1	1
min_top	-1	0	1	1	1	1

Key Moments - 3 Insights

Why do we push to min stack only when the new value is less or equal to the current min?

Because min stack keeps track of minimums. See step 3 in execution_table: 7 is not pushed to min stack since 7 > current min 3.

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

Min stack stays unchanged. See step 4: popped 7 from main stack but min stack remains same.

How does getMin() return the minimum value efficiently?

It returns the top of min stack instantly without scanning main stack, as shown in step 5.

Visual Quiz - 3 Questions

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

A [5, 3, 7]

B [5, 3]

C [3]

D [7]

💡 Hint

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

At which step does the main stack size decrease?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at 'Main Stack' column changes in execution_table.

If we push(2) after step 4, what happens to min stack?

A Min stack pops top

B Min stack remains unchanged

C 2 is pushed to min stack

D Min stack resets

💡 Hint

Recall min stack pushes new value if it is <= current min (see concept_flow).

Concept Snapshot

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

Full Transcript

Min Stack 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 min stack top, pop min stack too. getMin returns the top of min stack, giving minimum in constant time. This design ensures efficient minimum retrieval while maintaining stack behavior.