Min Stack Design in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of a Min Stack?

A Min Stack is a special stack that supports retrieving the minimum element in constant time, along with normal stack operations like push and pop.

intermediate

How does a Min Stack keep track of the minimum element efficiently?

It keeps an additional stack that stores the minimum values seen so far. When pushing, it compares the new value with the current minimum and updates accordingly.

intermediate

In Min Stack design, what happens when you pop an element that is the current minimum?

You also pop the top element from the minimum stack to update the current minimum to the previous minimum value.

beginner

Rust: Which data structure is commonly used to implement a stack for Min Stack design?

A Vec<T> (vector) is commonly used in Rust to implement a stack because it supports push and pop operations efficiently.

beginner

Why is it important for Min Stack operations to run in constant time?

Constant time operations ensure that retrieving the minimum element does not slow down the program, making the stack efficient for real-time or large-scale use.

What additional data structure is used in Min Stack design to track minimum values?

A Another stack

B Queue

C HashMap

D Linked list

Min Stack uses another stack to keep track of minimum values efficiently.

When pushing a new element, how do you update the minimum stack?

A Push the new element if it is smaller or equal to current minimum

B Always push the new element

C Never push to minimum stack

D Pop from minimum stack

You push the new element onto the minimum stack only if it is smaller or equal to the current minimum.

What happens to the minimum stack when popping the current minimum element?

A Do nothing

B Push a new minimum

C Pop from the minimum stack as well

D Clear the minimum stack

You pop from the minimum stack to update the current minimum after removing the minimum element.

Which Rust type is best suited for implementing a stack in Min Stack design?

A LinkedList<T>

B Vec<T>

C HashMap<K, V>

D Option<T>

Vec is efficient for stack operations like push and pop in Rust.

What is the time complexity of retrieving the minimum element in a Min Stack?

A O(n^2)

B O(n)

C O(log n)

D O(1)

Retrieving the minimum element in a Min Stack is done in constant time O(1).

Explain how a Min Stack maintains the minimum element during push and pop operations.

Think about how two stacks work together to track minimum.

Describe how you would implement a Min Stack in Rust using Vec.

Focus on stack operations and maintaining minimum stack.

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