Min Stack Design in DSA C++ - Execution Trace

Concept Flow - Min Stack Design

Push x

↓

Push x on main stack

↓

Compare x with current min

↓

Push x on min stack

↓

Do nothing on min stack

↓

Done

↓

Pop

↓

Pop from main stack

↓

Compare popped value with min stack top

↓

Pop from min stack

↓

Do nothing

↓

Done

↓

GetMin

↓

Return top of min stack

↓

Done

When pushing, add to main stack and update min stack if needed. When popping, remove from main stack and min stack if top matches. GetMin returns top of min stack.

Execution Sample

DSA C++

MinStack ms;
ms.push(5);
ms.push(3);
ms.push(7);
ms.pop();
int minVal = ms.getMin();

Push 5, 3, 7; pop top (7); get minimum value from stack.

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]	popped=7, main_top=3, min_top=3	Main: 3 -> 5 -> null Min: 3 -> 5 -> null
5	getMin()	[5,3]	[5,3]	min_top=3	Min value is 3
6	pop()	[5]	[5]	popped=3, main_top=5, min_top=5	Main: 5 -> null Min: 5 -> null
7	getMin()	[5]	[5]	min_top=5	Min value is 5
8	pop()	[]	[]	popped=5, stacks empty	Both stacks empty
9	getMin()	[]	[]	empty stacks	No min value, stack empty

💡 Execution stops after all operations are done.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 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]	[]	[]
main_top	null	5	3	7	3	3	5	5	null	null
min_top	null	5	3	3	3	3	5	5	null	null
popped_value	null	null	null	null	7	null	3	null	5	null
min_value	null	null	null	null	3	3	5	5	null	null

Key Moments - 3 Insights

Why do we push the new value onto the min stack only if it is less than or equal to the current min?

Because the min stack keeps track of the minimum values so far. If the new value is smaller or equal, it becomes the new minimum. This is shown in step 2 and 3 of the execution_table where 3 is pushed onto min stack because it is less than 5.

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 step 4 where 7 is popped from main stack but min stack remains unchanged.

How do we get the minimum value from the stack efficiently?

We get the minimum by looking at the top of the min stack without traversing the main stack. Step 5 shows getMin returning 3 instantly from min stack top.

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 null

💡 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 4

C Step 5

D Step 8

💡 Hint

Look for when popped_value equals min_top and min stack changes in execution_table.

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

A The min stack is cleared

B It stays the same

C The new value is pushed on min stack

D The min stack top is replaced

💡 Hint

Refer to step 2 in execution_table where pushing 3 updates min stack.

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

Full Transcript

Min Stack uses two stacks to keep track of values and minimums. When pushing, the value goes to the main stack. If it is smaller or equal to the current minimum, it also goes to the min stack. When popping, if the popped value equals the min stack's top, pop from min stack too. Getting the minimum is just reading the top of the min stack. This keeps minimum retrieval fast and simple.

Practice

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

easy

A. To store elements in a queue fashion

B. To retrieve the minimum element in constant time

C. To sort elements in ascending order

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 key 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 B

4. Quick Check:

   Min Stack purpose = retrieve minimum element fast [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 way to declare a stack of integers in C++?

easy

A. stack<int> s[];

B. stack s<int>;

C. stack<int> s;

D. stack<int> s()

Solution

1. Step 1: Recall C++ stack declaration syntax

   The correct syntax uses template with angle brackets and variable name after.

2. Step 2: Check each option

   stack<int> s; matches correct syntax: stack<int> s;. Others have syntax errors.

3. Final Answer:

   stack<int> s; -> Option C

4. Quick Check:

   C++ stack declaration = stack<int> s; [OK]

Hint: Use template syntax: stack<Type> variable; [OK]

Common Mistakes:

• Placing variable name inside angle brackets
• Using parentheses instead of semicolon
• Declaring as array without initialization

3. Consider the following C++ code snippet implementing a Min Stack push operation:

void push(int x) {
  s.push(x);
  if (minStack.empty() || x <= minStack.top()) {
    minStack.push(x);
  }
}

What will be the content of minStack after pushing the sequence [3, 5, 2, 2, 4]?

medium

A. [3, 5, 2, 2, 4]

B. [2, 2]

C. [3, 2]

D. [3, 2, 2]

Solution

1. Step 1: Trace push operations on minStack

   Push 3: minStack empty, push 3 -> [3] Push 5: 5 > top(3), no push -> [3] Push 2: 2 <= 3, push 2 -> [3, 2] Push 2: 2 <= 2, push 2 -> [3, 2, 2] Push 4: 4 > 2, no push -> [3, 2, 2]

2. Step 2: Confirm final minStack content

   minStack contains [3, 2, 2] after all pushes.

3. Final Answer:

   [3, 2, 2] -> Option D

4. Quick Check:

   minStack after pushes = [3, 2, 2] [OK]

Hint: Push to minStack only if new value ≤ current min [OK]

Common Mistakes:

• Pushing all elements to minStack
• Not pushing duplicates of min
• Confusing minStack with main stack

4. The following code snippet is intended to implement the pop() operation of a Min Stack. Identify the error:

void pop() {
  if (s.top() == minStack.top()) {
    minStack.pop();
  }
  s.pop();
}

medium

A. It does not check if stacks are empty before popping

B. It pops from minStack before popping from s, causing mismatch

C. It compares values incorrectly using == instead of <=

D. It should pop from s twice when values match

Solution

1. Step 1: Analyze pop operation safety

   The code pops from stacks without checking if they are empty, risking runtime errors.

2. Step 2: Identify missing safety checks

   Before calling top() or pop(), stacks should be checked for emptiness.

3. Final Answer:

   It does not check if stacks are empty before popping -> Option A

4. Quick Check:

   Pop safety requires empty checks [OK]

Hint: Always check stack empty before pop or top [OK]

Common Mistakes:

• Ignoring empty stack checks
• Misusing comparison operators
• Popping stacks in wrong order

5. You want to design a Min Stack that supports push, pop, top, and getMin all in O(1) time. Which approach below correctly achieves this with minimal extra space?

hard

A. Use one stack to store values and a second stack to store minimums only when a new minimum is pushed

B. Use one stack and sort it after each push to find minimum

C. Use two stacks: one for values and one for all values pushed, then find min by scanning

D. Use a queue to store values and a stack to store minimums

Solution

1. Step 1: Understand O(1) min retrieval requirement

   To get minimum in constant time, we must track minimums during push/pop without scanning.

2. Step 2: Evaluate approaches

   Use one stack to store values and a second stack to store minimums only when a new minimum is pushed uses a second stack to store minimums only when a new minimum appears, saving space and ensuring O(1) operations.

3. Final Answer:

   Use one stack to store values and a second stack to store minimums only when a new minimum is pushed -> Option A

4. Quick Check:

   Min Stack with minimal space = two stacks, min pushed selectively [OK]

Hint: Push min only when new min found to save space [OK]

Common Mistakes:

• Sorting stack after each push (slow)
• Scanning stack to find min (not O(1))
• Using queue which breaks stack order