Min Stack Design in DSA Rust

Mental Model

A Min Stack keeps track of the smallest value at every point so you can get the minimum quickly.

Analogy: Imagine a stack of plates where each plate also has a note showing the smallest plate below it. When you add or remove plates, you update the note so you always know the smallest plate on top.

Stack top
  ↓
[7, min=3] -> [3, min=3] -> [5, min=5] -> null

Dry Run Walkthrough

Input: Push 5, Push 3, Push 7, Get Min, Pop, Get Min

Goal: Show how the stack updates and how min is tracked after each operation

Step 1: Push 5 onto stack

[5, min=5] -> null

Why: First element is the minimum so far

Step 2: Push 3 onto stack

[3, min=3] -> [5, min=5] -> null

Why: 3 is smaller than previous min 5, update min to 3

Step 3: Push 7 onto stack

[7, min=3] -> [3, min=3] -> [5, min=5] -> null

Why: 7 is not smaller than min 3, keep min as 3

Step 4: Get Min value

[7, min=3] -> [3, min=3] -> [5, min=5] -> null

Why: Top node min is 3, so min is 3

Step 5: Pop top element (7)

[3, min=3] -> [5, min=5] -> null

Why: Remove top, min remains 3 from next node

Step 6: Get Min value

[3, min=3] -> [5, min=5] -> null

Why: Top node min is 3, so min is 3

Result:

[3, min=3] -> [5, min=5] -> null
Minimum value: 3

Annotated Code

DSA Rust

struct MinStack {
    stack: Vec<(i32, i32)>,
}

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

    fn push(&mut self, val: i32) {
        let min = match self.stack.last() {
            Some(&(_, current_min)) => if val < current_min { val } else { current_min },
            None => val,
        };
        self.stack.push((val, min));
    }

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

    fn top(&self) -> Option<i32> {
        self.stack.last().map(|&(val, _)| val)
    }

    fn get_min(&self) -> Option<i32> {
        self.stack.last().map(|&(_, min)| min)
    }
}

fn main() {
    let mut min_stack = MinStack::new();
    min_stack.push(5);
    min_stack.push(3);
    min_stack.push(7);
    println!("Minimum value: {}", min_stack.get_min().unwrap());
    min_stack.pop();
    println!("Minimum value: {}", min_stack.get_min().unwrap());
}

let min = match self.stack.last() { ... };

Determine new min by comparing pushed value with current min

self.stack.push((val, min));

Push value and current min as a pair onto stack

self.stack.pop();

Remove top element from stack

self.stack.last().map(|&(_, min)| min)

Get min value from top element's stored min

Output

Minimum value: 3

Minimum value: 3

Complexity Analysis

Time: O(1) for push, pop, and get_min because we store min with each element

Space: O(n) because we store each element with its min value

vs Alternative: Compared to scanning stack for min each time (O(n)), this is much faster at O(1) but uses extra space

Edge Cases

Empty stack when calling get_min or top

Returns None safely without crashing

DSA Rust

self.stack.last().map(|&(_, min)| min)

Push duplicate minimum values

Min is correctly tracked and updated for each duplicate

DSA Rust

let min = match self.stack.last() { ... }

Pop until stack is empty

Stack becomes empty and get_min returns None

DSA Rust

self.stack.pop();

When to Use This Pattern

When a problem asks for retrieving the minimum value in a stack quickly, use the Min Stack pattern to track minimums alongside values.

Common Mistakes

Mistake: Only storing values without tracking min leads to O(n) min retrieval.
Fix: Store the current min with each pushed value to get O(1) min retrieval.

Mistake: Updating min incorrectly by not comparing with previous min.
Fix: Always compare new value with current min before updating.

Summary

Keeps track of the minimum value in a stack at all times.

Use when you need to get the minimum value quickly while pushing and popping.

Store the minimum value with each element to get constant time min retrieval.

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