Min Stack Design in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to push a value onto the stack.

DSA Rust

fn push(&mut self, val: i32) {
    self.stack.push([1]);
}

Drag options to blanks, or click blank then click option'

A0

Bval

Cself.stack.len()

Dself.min_stack.last().unwrap()

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing the wrong variable instead of 'val'.

Using stack length instead of the value.

We push the given value 'val' onto the main stack.

2fill in blank

medium

Complete the code to get the current minimum value from the min stack.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Apop

Bfirst

Clast

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' which removes the element.

Using 'first' which gets the bottom element.

The 'last' method returns the top element of the min stack without removing it.

3fill in blank

hard

Fix the error in the pop method to correctly update both stacks.

DSA Rust

fn pop(&mut self) -> Option<i32> {
    let val = self.stack.pop()?;
    if val == *self.min_stack.[1]().unwrap() {
        self.min_stack.pop();
    }
    Some(val)
}

Drag options to blanks, or click blank then click option'

Aremove

Bpop

Cfirst

Dlast

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' which removes the element prematurely.

Using 'first' which checks the wrong element.

We compare with the top of min_stack using 'last' without removing it.

4fill in blank

hard

Fill both blanks to correctly update the min stack when pushing a new value.

DSA Rust

fn push(&mut self, val: i32) {
    self.stack.push(val);
    if self.min_stack.is_empty() || val [1] *self.min_stack.[2]().unwrap() {
        self.min_stack.push(val);
    }
}

Drag options to blanks, or click blank then click option'

A<=

B>=

Clast

Dfirst

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' instead of '<=' causing wrong min updates.

Using 'first' instead of 'last' to peek top element.

We push 'val' to min_stack if it is less than or equal to the current minimum (top of min_stack).

5fill in blank

hard

Fill the blank to implement a method that returns the top element of the stack safely.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Alast

Bfirst

Cpop

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'pop' which removes the element.

Using 'first' which gets the bottom element.

The 'last' method returns the top element without removing it, and 'copied' converts from reference to value.

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