Why Min Stack Design in DSA Rust?

The Big Idea

What if you could always know the smallest item instantly, no matter how many you add or remove?

The Scenario

Imagine you have a stack of books and you want to quickly find the smallest book without checking each one every time.

The Problem

Manually searching for the smallest book each time is slow and tiring. You might miss the smallest one or waste time flipping through all books repeatedly.

The Solution

A Min Stack keeps track of the smallest item as you add or remove books, so you always know the smallest book instantly without searching.

Before vs After

✗ Before

fn get_min(stack: &Vec<i32>) -> Option<i32> {
    stack.iter().min().cloned()
}

// Need to scan entire stack every time

✓ After

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

// min_stack always holds current minimum

What It Enables

You can get the smallest item in constant time while still using the stack normally.

Real Life Example

Tracking the lowest price of stocks in a trading app while adding and removing price points quickly.

Key Takeaways

Manual search for minimum is slow and error-prone.

Min Stack stores minimums to give instant access.

Useful when you need fast minimum queries alongside stack operations.

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