Min Stack Design in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Min Stack after Push and Pop Operations

Consider a Min Stack that supports push, pop, top, and get_min operations. What is the output of the get_min calls after the following operations?

push(3)
push(5)
get_min()
push(2)
push(1)
get_min()
pop()
get_min()
pop()
top()

DSA Rust

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

impl MinStack {
    fn new() -> Self {
        MinStack { stack: Vec::new(), min_stack: Vec::new() }
    }

    fn push(&mut self, val: i32) {
        self.stack.push(val);
        if self.min_stack.is_empty() || val <= *self.min_stack.last().unwrap() {
            self.min_stack.push(val);
        }
    }

    fn pop(&mut self) {
        if let Some(top) = self.stack.pop() {
            if top == *self.min_stack.last().unwrap() {
                self.min_stack.pop();
            }
        }
    }

    fn top(&self) -> Option<i32> {
        self.stack.last().copied()
    }

    fn get_min(&self) -> Option<i32> {
        self.min_stack.last().copied()
    }
}

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

A [Some(3), Some(1), Some(2), Some(3)]

B [Some(3), Some(1), Some(3), Some(5)]

C [Some(3), Some(2), Some(2), Some(3)]

D [Some(3), Some(1), Some(2), Some(5)]

💡 Hint

Track the minimum values on a separate stack and update it on push and pop.

The min stack keeps track of minimums. After pushing 3 and 5, min is 3. After pushing 2 and 1, min is 1. Popping 1 removes it from min stack, min becomes 2. Popping 2 removes it, top is 5.

🧠 Conceptual

intermediate

Why Use Two Stacks in Min Stack Design?

Why does a Min Stack implementation typically use two stacks instead of one?

A To separate even and odd numbers for faster retrieval.

B To keep track of all elements and their insertion order separately.

C To maintain the current minimum value at each state efficiently.

D To store elements and their indices for quick access.

💡 Hint

Think about how to get the minimum value quickly after each operation.

One stack stores all elements; the other keeps track of minimum values so get_min() is O(1).

🔧 Debug

advanced

Identify the Bug in Min Stack Pop Method

What error will occur when running this pop method in a Min Stack implementation?

fn pop(&mut self) {
    let top = self.stack.pop().unwrap();
    if top == self.min_stack.last().unwrap() {
        self.min_stack.pop();
    }
}

A Panic if pop is called on an empty stack due to unwrap on None.

B No error; code runs correctly for all cases.

C Logical error: min_stack is never updated.

D Compilation error because of missing return type.

💡 Hint

Consider what happens if pop is called when the stack is empty.

Calling unwrap() on None causes panic if stack is empty. Safe code should check before popping.

❓ Predict Output

advanced

Output of Min Stack with Duplicate Minimums

What is the output of the get_min calls after these operations on a Min Stack?

push(2)
push(2)
push(1)
push(1)
pop()
get_min()
pop()
get_min()

DSA Rust

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

impl MinStack {
    fn new() -> Self {
        MinStack { stack: Vec::new(), min_stack: Vec::new() }
    }

    fn push(&mut self, val: i32) {
        self.stack.push(val);
        if self.min_stack.is_empty() || val <= *self.min_stack.last().unwrap() {
            self.min_stack.push(val);
        }
    }

    fn pop(&mut self) {
        if let Some(top) = self.stack.pop() {
            if top == *self.min_stack.last().unwrap() {
                self.min_stack.pop();
            }
        }
    }

    fn get_min(&self) -> Option<i32> {
        self.min_stack.last().copied()
    }
}

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

A [Some(2), Some(1)]

B [Some(1), Some(2)]

C [Some(1), Some(1)]

D [Some(2), Some(2)]

💡 Hint

Remember how duplicate minimums are handled in min_stack.

After popping one '1', min is still 1 because of duplicate. After popping second '1', min becomes 2.

🚀 Application

expert

Design a Min Stack with O(1) Space Optimization

Which approach allows implementing a Min Stack that uses only one stack and O(1) extra space for tracking the minimum?

A Store the difference between the current value and the minimum on the stack and update minimum accordingly.

B Use a queue instead of a stack to track minimum values.

C Keep a sorted list of all elements to find minimum in O(1).

D Store all elements twice to maintain minimum history.

💡 Hint

Think about encoding minimum information within the stack elements themselves.

Storing differences allows tracking minimum without extra stack, updating minimum on push/pop in O(1) space.

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