Min Stack Design in DSA C# - 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 equals min stack top

↓

If yes, pop min stack

↓

GetMin returns top of min stack

The Min Stack keeps track of all values and the current minimum using two stacks. When pushing, it updates the min stack if needed. When popping, it updates the min stack accordingly. GetMin returns the current minimum.

Execution Sample

DSA C#

MinStack stack = new MinStack();
stack.Push(5);
stack.Push(3);
stack.Push(7);
stack.Pop();
int min = stack.GetMin();

This code pushes 5, 3, 7 onto the stack, pops the top (7), then gets the current minimum value.

Execution Table

Step	Operation	Main Stack	Min Stack	Pointer Changes	Visual State
1	Push 5	[5]	[5]	Main top=5, Min top=5	Main: 5 -> null, Min: 5 -> null
2	Push 3	[5,3]	[5,3]	Main top=3, Min top=3	Main: 3 -> 5 -> null, Min: 3 -> 5 -> null
3	Push 7	[5,3,7]	[5,3]	Main top=7, Min top=3	Main: 7 -> 3 -> 5 -> null, Min: 3 -> 5 -> null
4	Pop	[5,3]	[5,3]	Pop 7 from main, min unchanged	Main: 3 -> 5 -> null, Min: 3 -> 5 -> null
5	GetMin	[5,3]	[5,3]	Min top=3 returned	Main: 3 -> 5 -> null, Min: 3 -> 5 -> null
6	Pop	[5]	[5]	Pop 3 from main and min	Main: 5 -> null, Min: 5 -> null
7	GetMin	[5]	[5]	Min top=5 returned	Main: 5 -> null, Min: 5 -> null
8	Pop	[]	[]	Pop 5 from main and min	Main: null, Min: null
9	GetMin	[]	[]	Min stack empty, no min	Main: null, Min: null

💡 Execution stops after all operations are done.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
Main Stack	[]	[5]	[5,3]	[5,3,7]	[5,3]	[5,3]	[5]	[5]	[]	[]
Min Stack	[]	[5]	[5,3]	[5,3]	[5,3]	[5,3]	[5]	[5]	[]	[]
Top of Min Stack	null	5	3	3	3	3	5	5	null	null

Key Moments - 3 Insights

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

Because the min stack keeps track of the current minimum values. When a new value is smaller or equal, it becomes the new minimum, so we push it to the min stack. This is shown in execution_table rows 1 and 2 where min stack updates.

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

The min stack does not change because the popped value is not the minimum. This is shown in execution_table row 4 where popping 7 does not change the min stack.

How does GetMin always return the current minimum quickly?

GetMin returns the top of the min stack, which always holds the current minimum. This is shown in execution_table rows 5 and 7 where min stack top is returned immediately.

Visual Quiz - 3 Questions

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

A 7

B 3

C 5

D None

💡 Hint

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

At which step does the min stack pop a value?

A Step 6

B Step 5

C Step 4

D Step 3

💡 Hint

Look for when the min stack changes from [5,3] to [5] in execution_table.

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

A It stays the same

B It pops the top

C It pushes the new smaller value

D It clears all values

💡 Hint

Refer to concept_flow and execution_table steps 1 and 2.

Concept Snapshot

Min Stack Design:
- Use two stacks: main stack and min stack
- Push: add to main stack; if new value <= min stack top, push to min stack
- Pop: remove from main stack; if popped == min stack top, pop min stack
- GetMin: return top of min stack
- Allows O(1) min retrieval at any time

Full Transcript

Min Stack Design uses two stacks to keep track of values and the minimum value efficiently. When pushing a value, it is added to the main stack. If this value is smaller or equal to the current minimum, it is also pushed onto the min stack. When popping, if the popped value equals the min stack's top, it is popped from the min stack as well. The GetMin operation returns the top of the min stack, which is always the current minimum. This design ensures constant time retrieval of the minimum value. The execution table shows step-by-step how the stacks change with each operation, and the variable tracker records the state of both stacks after each step.

Practice

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

easy

A. To retrieve the minimum element in constant time

B. To sort elements in ascending order

C. To store elements in a queue fashion

D. To reverse the order of elements

Solution

1. Step 1: Understand the Min Stack concept

   A Min Stack is designed to keep track of the minimum element efficiently.

2. Step 2: Identify the main feature

   It allows retrieving the minimum element in constant time, unlike a normal stack.

3. Final Answer:

   To retrieve the minimum element in constant time -> Option A

4. Quick Check:

   Min Stack = fast minimum retrieval [OK]

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

Common Mistakes:

• Confusing Min Stack with sorting
• Thinking it behaves like a queue
• Assuming it reverses elements

2. Which of the following is the correct C# method signature to push an integer val onto a Min Stack?

easy

A. public void Push(string val)

B. public int Push(int val)

C. void Push()

D. public void Push(int val)

Solution

1. Step 1: Check method return type and parameters

   Push method should not return a value, so return type is void, and it takes an int parameter.

2. Step 2: Match the correct signature

   public void Push(int val) matches: public void Push(int val)

3. Final Answer:

   public void Push(int val) -> Option D

4. Quick Check:

   Push method = void + int parameter [OK]

Hint: Push returns void and takes int parameter [OK]

Common Mistakes:

• Using wrong return type like int
• Missing parameter in method
• Using wrong parameter type like string

3. Given the following operations on a Min Stack:

MinStack minStack = new MinStack();
minStack.Push(3);
minStack.Push(5);
minStack.Push(2);
minStack.Push(1);
minStack.Pop();
int min = minStack.GetMin();
Console.WriteLine(min);

What will be printed?

medium

A. 1

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace the stack after each operation

   Push 3 -> stack: [3], min=3 Push 5 -> stack: [3,5], min=3 Push 2 -> stack: [3,5,2], min=2 Push 1 -> stack: [3,5,2,1], min=1 Pop -> removes 1, stack: [3,5,2], min=2

2. Step 2: GetMin after pop

   Minimum is now 2 after popping 1.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Min after pop = 2 [OK]

Hint: Pop removes min, next min updates correctly [OK]

Common Mistakes:

• Assuming min stays 1 after pop
• Confusing stack top with min
• Ignoring pop effect on min

4. Consider this buggy Min Stack pop method:

public void Pop() {
    if(stack.Count > 0) {
        stack.Pop();
        minStack.Pop();
    }}

What is the main issue with this implementation?

medium

A. It does not check if stack is empty before popping

B. It pushes elements instead of popping

C. It pops from minStack even when the popped element is not the minimum

D. It returns a value but method is void

Solution

1. Step 1: Understand the role of minStack

   minStack should only pop when the popped element equals the current minimum.

2. Step 2: Identify the bug

   This code pops minStack every time, even if the popped element is not minimum, causing incorrect min tracking.

3. Final Answer:

   It pops from minStack even when the popped element is not the minimum -> Option C

4. Quick Check:

   Pop minStack only if popped element == min [OK]

Hint: Pop minStack only if popped element equals current min [OK]

Common Mistakes:

• Always popping minStack blindly
• Not checking stack emptiness (not in this code)
• Confusing push and pop operations

5. You want to design a Min Stack that supports Push, Pop, Top, and GetMin 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 single stack and sort it after each push

C. Use a queue to track minimum elements

D. Store all elements in a list and scan for min on GetMin

Solution

1. Step 1: Analyze time complexity requirements

   All operations must be O(1), so sorting or scanning is too slow.

2. Step 2: Identify suitable data structure

   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 tracking [OK]

Hint: Two stacks track elements and minimums efficiently [OK]

Common Mistakes:

• Sorting stack after each push (slow)
• Using queue instead of stack
• Scanning list for min on each GetMin