Min Stack Design in DSA Rust - Execution Trace

Concept Flow - Min Stack Design

Push value

↓

Compare with current min

↓

Push value to min stack

↓

Push current min again

↓

Update main stack

↓

Pop value

↓

Pop from min stack

↓

Get min

↓

Return top of min stack

When pushing, compare new value with current min and push the smaller to min stack. On pop, pop both stacks. Min is top of min stack.

Execution Sample

DSA Rust

stack.push(3);
stack.push(5);
stack.push(2);
stack.pop();
min = stack.get_min();

Push 3, 5, 2; pop top; get current minimum value.

Execution Table

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

💡 All operations complete; stacks empty at end.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
Main Stack	[]	[3]	[3,5]	[3,5,2]	[3,5]	[3,5]	[3]	[3]	[]	[]
Min Stack	[]	[3]	[3,3]	[3,3,2]	[3,3]	[3,3]	[3]	[3]	[]	[]
Min Value	None	3	3	2	3	3	3	3	None	None

Key Moments - 3 Insights

Why do we push the current minimum again onto the min stack when the new value is not smaller?

Because the min stack must always have the minimum value corresponding to each element in the main stack. See step 2 in execution_table where 5 is pushed but min stack repeats 3.

What happens to the min stack when we pop from the main stack?

We pop from the min stack as well to keep both stacks synchronized. See step 4 where both stacks pop their top elements.

How do we get the current minimum value efficiently?

By looking at the top of the min stack, which always holds the minimum for the current main stack state. See step 5 where get_min returns 3 from min stack top.

Visual Quiz - 3 Questions

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

A 3

B 2

C 5

D None

💡 Hint

Check the Min Stack column at step 3 in execution_table.

At which step does the main stack become empty?

A Step 8

B Step 7

C Step 9

D Step 6

💡 Hint

Look at the Main Stack column in execution_table to find when it becomes [].

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

A Do not push anything on min stack

B Push the old min value again

C Push the new smaller value on min stack

D Clear the min stack

💡 Hint

Refer to concept_flow and step 3 in execution_table where 2 is pushed as new min.

Concept Snapshot

Min Stack Design:
- Use two stacks: main and min stack
- Push: add value to main; push min(value, current min) to min stack
- Pop: remove top from both stacks
- Get min: top of min stack
- Keeps track of min in O(1) time

Full Transcript

This visualization shows how a Min Stack works using two stacks. When pushing a value, we compare it with the current minimum and push the smaller one onto the min stack. Both stacks grow together. When popping, we remove the top from both stacks to keep them synchronized. The current minimum is always the top of the min stack. The execution table traces pushing 3, 5, 2, popping, and getting the minimum step by step, showing the state of both stacks and the minimum value. Key moments clarify why the min stack duplicates values and how popping affects both stacks. The quiz tests understanding of min stack top values, empty stack state, and pushing smaller values. This design allows retrieving the minimum value in constant time.

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 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 A

4. Quick Check:

   Min Stack = fast minimum retrieval [OK]

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

Common Mistakes:

• Thinking it sorts elements
• Confusing with queue behavior
• Assuming it reverses elements

2. Which Rust syntax correctly declares a struct for a Min Stack with two vectors named stack and min_stack?

easy

A. struct MinStack { stack: Vec, min_stack: Vec }

B. struct MinStack { stack: [i32], min_stack: [i32] }

C. struct MinStack { stack: Vec<i32>, min_stack: Vec<i32> }

D. struct MinStack { stack: Vec<i32>, min_stack: Vec<i64> }

Solution

1. Step 1: Check Rust vector syntax

   Vectors in Rust are declared as Vec<Type>, so Vec<i32> is correct for 32-bit integers.

2. Step 2: Validate struct field types

   struct MinStack { stack: Vec<i32>, min_stack: Vec<i32> } uses Vec<i32> for both fields, which is correct syntax and consistent types.

3. Final Answer:

   struct MinStack { stack: Vec<i32>, min_stack: Vec<i32> } -> Option C

4. Quick Check:

   Vec<i32> syntax = correct struct fields [OK]

Hint: Use Vec<i32> for integer vectors in Rust structs [OK]

Common Mistakes:

• Using array syntax [i32] instead of Vec<i32>
• Omitting type parameters in Vec
• Mixing different integer types

3. Given the following Rust code snippet for a Min Stack, what will be printed after the operations?

let mut min_stack = MinStack::new();
min_stack.push(3);
min_stack.push(5);
min_stack.push(2);
min_stack.push(1);
min_stack.pop();
println!("{}", min_stack.get_min());

medium

A. 1

B. 2

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 last pushed element (1), min updates to previous min (2)

   After popping 1, minimum is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Pop last min updates min to 2 [OK]

Hint: Pop removes last min, so min updates to previous min [OK]

Common Mistakes:

• Assuming min stays 1 after pop
• Confusing push order
• Ignoring min stack update on pop

4. Identify the bug in this Rust Min Stack pop method and choose the correct fix:

fn pop(&mut self) {
    self.stack.pop();
    self.min_stack.pop();
}

medium

A. Clear min_stack when stack is empty

B. No bug; code is correct

C. Pop twice from stack to sync with min_stack

D. Pop from min_stack only if popped element equals current min

Solution

1. Step 1: Understand pop logic in Min Stack

   Pop from stack always removes top element. Min stack should only pop if popped element equals current min.

2. Step 2: Identify bug and fix

   Current code pops min_stack unconditionally, which breaks min tracking. Fix is to pop min_stack only when needed.

3. Final Answer:

   Pop from min_stack only if popped element equals current min -> Option D

4. Quick Check:

   Conditional min_stack pop fixes min tracking [OK]

Hint: Pop min_stack only if popped value equals current min [OK]

Common Mistakes:

• Popping min_stack unconditionally
• Popping stack twice
• Not handling empty stack cases

5. You want to design a Min Stack in Rust that supports push, pop, and get_min all in O(1) time. Which approach below correctly achieves this?

hard

A. Use two stacks: one for all elements, one for current minimums updated on push and pop

B. Use a linked list and sort it after each push

C. Use a queue to store elements and a variable to track min updated on pop

D. Use one stack and scan all elements to find min on each get_min call

Solution

1. Step 1: Analyze time complexity requirements

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

2. Step 2: Identify data structure approach

   Two stacks approach keeps track of minimums efficiently by pushing current min on min_stack during push and popping accordingly.

3. Final Answer:

   Use two stacks: one for all elements, one for current minimums updated on push and pop -> Option A

4. Quick Check:

   Two stacks = O(1) min tracking [OK]

Hint: Two stacks track elements and min for O(1) operations [OK]

Common Mistakes:

• Using scanning for min on each call
• Using queue instead of stack
• Sorting after each push