Min Stack Design in DSA Rust - Build from Scratch

Min Stack Design

📖 Scenario: Imagine you are building a simple calculator app that needs to keep track of numbers pushed onto a stack. You want to quickly find the smallest number in the stack at any time without searching through all numbers.

🎯 Goal: Build a MinStack data structure in Rust that supports pushing numbers, popping the top number, and retrieving the current minimum number efficiently.

📋 What You'll Learn

Create a struct called MinStack with two vectors: stack and min_stack.

Add a method push(&mut self, val: i32) that adds val to stack and updates min_stack with the current minimum.

Add a method pop(&mut self) -> Option that removes and returns the top element from stack and updates min_stack accordingly.

Add a method get_min(&self) -> Option that returns the current minimum number from min_stack.

Print the minimum after some push and pop operations.

💡 Why This Matters

🌍 Real World

MinStack is useful in calculators, undo features, and algorithms that need quick access to minimum values in a changing dataset.

💼 Career

Understanding stack design and optimization is important for software engineers working on performance-critical applications and data structure implementations.

1

Create the MinStack struct with two vectors

Create a struct called MinStack with two fields: stack and min_stack, both of type Vec. Also implement a new() method that returns an empty MinStack.

DSA Rust

struct MinStack {
    stack: Vec,
    min_stack: Vec,
}

impl MinStack {
    // Create a new empty MinStack
    fn new() -> Self {
        // Your code here
    }
}

Hint

Use Vec::new() to create empty vectors for both stack and min_stack.

2

Add the push method to add elements and track minimum

Add a method push(&mut self, val: i32) to MinStack. It should push val onto stack. Then push val onto min_stack if min_stack is empty or val is less than or equal to the current minimum (last element of min_stack). Otherwise, push the current minimum again to min_stack.

DSA Rust

struct MinStack {
    stack: Vec,
    min_stack: Vec,
}

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

    // Add push method here
    fn push(&mut self, val: i32) {
        // Your code here
    }
}

Hint

Remember to push the current minimum again if the new value is not smaller.

3

Add pop and get_min methods

Add a method pop(&mut self) -> Option that removes and returns the top element from stack and also pops from min_stack. Add a method get_min(&self) -> Option that returns the last element of min_stack without removing it.

DSA Rust

struct MinStack {
    stack: Vec,
    min_stack: Vec,
}

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  Option {
        // Your code here
    }

    // Add get_min method here
    fn get_min(&self) -> Option {
        // Your code here
    }
}

Hint

Pop from both vectors in pop. Use last().copied() to get the minimum without removing it.

4

Test MinStack by pushing, popping, and printing minimum

Create a MinStack instance called min_stack. Push the numbers 5, 3, 7, and 2 in that order. Print the minimum using get_min(). Then pop one element and print the minimum again.

DSA Rust

struct MinStack {
    stack: Vec,
    min_stack: Vec,
}

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  Option {
        self.min_stack.pop();
        self.stack.pop()
    }

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

fn main() {
    let mut min_stack = MinStack::new();
    // Push 5, 3, 7, 2
    // Print minimum
    // Pop one element
    // Print minimum again
    // Your code here
}

Hint

Use println!("{}", min_stack.get_min().unwrap()) to print the minimum. Remember to unwrap the Option.

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