Min Stack

The Problem: A normal stack allows push, pop, and peek in $O(1)$. But if I ask you: “What is the smallest number currently in the stack?”, you would normally have to scan the whole list, which is $O(N)$. That is too slow.

The Goal: Design a stack that supports get_min() in $O(1)$.

The Logic: You cannot just store one variable min_val because if you pop the minimum element, you need to know what the previous minimum was.

The Solution: Use Two Stacks.

1. Main Stack: Stores the actual data.
2. Min Stack: Stores the minimum value seen so far.

Example Trace: push(5), push(2), push(8), push(1), pop()

Operation	Value	Main Stack	Min Stack (Tracks min so far)	Current Min
push(5)	5	[5]	[5]	5
push(2)	2	[5, 2]	[5, 2] (Since $2<5$)	2
push(8)	8	[5, 2, 8]	[5, 2, 2] (Since $8>2$, repeat 2)	2
push(1)	1	[5, 2, 8, 1]	[5, 2, 2, 1]	1
pop()	-	[5, 2, 8]	[5, 2, 2] (Pop both!)	2

Note: In the push(8) step, we pushed 2 again onto the Min Stack. Why? To keep the stacks the same height, making pop easy. Alternatively, you can only push to Min Stack if the new value is $\le$ current min.

Constraints:

• You must use the “Two Stack” approach (or a Tuple approach in Python).
• Do not use min(self.items) (That cheats and is slow).

from typing import Any, Optional
 
 
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
 
    def push(self, item: Any) -> None:
        self.stack.append(item)
 
        # If min_stack is empty OR new item is smaller, push it.
        # Otherwise, duplicate the current minimum to keep stacks synced.
        if not self.min_stack or item < self.min_stack[-1]:
            self.min_stack.append(item)
        else:
            self.min_stack.append(self.min_stack[-1])
 
    def pop(self) -> Optional[Any]:
        if not self.stack:
            return None
        self.min_stack.pop()
        return self.stack.pop()
 
    def peek(self) -> Optional[Any]:
        if not self.stack:
            return None
        return self.stack[-1]
 
    def get_min(self) -> Optional[Any]:
        if not self.min_stack:
            return None
        return self.min_stack[-1]

pub struct MinStack {
    stack: Vec<i32>,
    min_stack: Vec<i32>,
}
 
impl MinStack {
    pub fn new() -> Self {
        Self {
            stack: Vec::new(),
            min_stack: Vec::new(),
        }
    }
 
    pub fn push(&mut self, item: i32) {
        self.stack.push(item);
 
        // If min_stack is empty OR item is smaller than current min
        if self.min_stack.is_empty() || item < *self.min_stack.last().unwrap() {
            self.min_stack.push(item);
        } else {
            // Duplicate the previous min so both stacks have same height
            let previous_min = *self.min_stack.last().unwrap();
            self.min_stack.push(previous_min);
        }
    }
 
    pub fn pop(&mut self) -> Option<i32> {
        // Pop both to keep them synchronized
        self.min_stack.pop();
        self.stack.pop()
    }
 
    pub fn peek(&self) -> Option<&i32> {
        self.stack.last()
    }
 
    pub fn get_min(&self) -> Option<&i32> {
        self.min_stack.last()
    }
}