Min Stack Design in DSA Rust - Time & Space Complexity

Time Complexity: Min Stack Design

O(1)

Understanding Time Complexity

We want to understand how fast the Min Stack operations run as we add more items.

How does the time to push, pop, or get the minimum change when the stack grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

impl MinStack {
    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 {
        self.min_stack.last().copied()
    }
}
    

This code keeps track of the minimum value in the stack at all times using a helper stack.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each push and pop operation works on the top of the stacks without loops.
• How many times: Each operation runs once per call, no repeated loops inside.

How Execution Grows With Input

Each push or pop does a fixed number of steps regardless of stack size.

Input Size (n)	Approx. Operations per push/pop
10	2-3 steps
100	2-3 steps
1000	2-3 steps

Pattern observation: The number of steps stays about the same no matter how big the stack is.

Final Time Complexity

Time Complexity: O(1)

This means each push, pop, or get_min operation takes the same short time no matter how many items are in the stack.

Common Mistake

[X] Wrong: "Finding the minimum must check all items, so it takes longer as the stack grows."

[OK] Correct: The min stack keeps track of minimums as we go, so get_min just looks at the top of min_stack instantly.

Interview Connect

Knowing how to keep track of minimums efficiently shows you can design smart data structures that save time.

Self-Check

"What if we stored minimums only when they change, not every time? How would that affect time complexity?"

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