Min Stack

Medium

Python

class MinStack:
    def __init__(self):
        self.stack=[]; self.min_stack=[]
    def push(self,val):
        self.stack.append(val)
        mn=min(val,self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(mn)
    def pop(self): self.stack.pop(); self.min_stack.pop()
    def top(self): return self.stack[-1]
    def get_min(self): return self.min_stack[-1]

Java

class MinStack{
    Stack<Integer> stack=new Stack<>(),minStack=new Stack<>();
    public void push(int val){
        stack.push(val);
        minStack.push(minStack.isEmpty()?val:Math.min(val,minStack.peek()));
    }
    public void pop(){stack.pop();minStack.pop();}
    public int top(){return stack.peek();}
    public int getMin(){return minStack.peek();}
}

Key Insight

stack[-1] for peek vs Java peek(). list as stack vs Stack class.

Python → Java Differences

stack[-1] vs peek()
list as stack vs Stack class
Aux min stack identical

Python

class MinStack:
    def __init__(self):
        self.stack=[]; self.min_stack=[]
    def push(self,val):
        self.stack.append(val)
        mn=min(val,self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(mn)
    def pop(self): self.stack.pop(); self.min_stack.pop()
    def top(self): return self.stack[-1]
    def get_min(self): return self.min_stack[-1]

Java

class MinStack{
    Stack<Integer> stack=new Stack<>(),minStack=new Stack<>();
    public void push(int val){
        stack.push(val);
        minStack.push(minStack.isEmpty()?val:Math.min(val,minStack.peek()));
    }
    public void pop(){stack.pop();minStack.pop();}
    public int top(){return stack.peek();}
    public int getMin(){return minStack.peek();}
}

Algorithm Steps

1. Maintain auxiliary min stack
2. Push current min
3. Pop both together

All Stacks & Queues Next →