Design Min Stack — O(1) Minimum with Auxiliary Stack

Problem

Design a stack that supports:

push(val) — push element
pop() — remove top element
top() — get top element
getMin() — retrieve minimum element

All operations must be O(1).

Key Insight — Parallel Min Stack

Maintain a second stack that tracks the current minimum at each level. When pushing, push min(val, min_stack.top()) to the min stack.

Solutions

Python

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        self.min_stack.append(val if not self.min_stack else min(val, self.min_stack[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

JavaScript

class MinStack {
    constructor() { this.s = []; this.m = []; }
    push(v) { this.s.push(v); this.m.push(Math.min(v, this.m.length ? this.m[this.m.length-1] : v)); }
    pop() { this.s.pop(); this.m.pop(); }
    top() { return this.s[this.s.length-1]; }
    getMin() { return this.m[this.m.length-1]; }
}

Java

import java.util.*;
class MinStack {
    Deque<Integer> s=new ArrayDeque<>(), m=new ArrayDeque<>();
    public void push(int v) { s.push(v); m.push(m.isEmpty()?v:Math.min(v,m.peek())); }
    public void pop() { s.pop(); m.pop(); }
    public int top() { return s.peek(); }
    public int getMin() { return m.peek(); }
}

C++

#include <stack>
using namespace std;
class MinStack {
    stack<int> s, m;
public:
    void push(int v) { s.push(v); m.push(m.empty()?v:min(v,m.top())); }
    void pop() { s.pop(); m.pop(); }
    int top() { return s.top(); }
    int getMin() { return m.top(); }
};

C

int stk[10001], mstk[10001], sz=0;
void push(int v){ stk[sz]=v; mstk[sz]=(sz==0)?v:(v<mstk[sz-1]?v:mstk[sz-1]); sz++; }
void pop(){ sz--; }
int top(){ return stk[sz-1]; }
int getMin(){ return mstk[sz-1]; }

Complexity

Operation	Time	Space
All ops	O(1)	O(N)