Min Stack LeetCode Solution (Medium) (2026)

Q: What is the optimal time and space complexity for Min Stack?

The optimal solution for Min Stack achieves O(1) all ops runtime complexity and requires O(n) auxiliary space. Every operation does constant work — a push or pop plus an O(1) min comparison — so all four methods are O(1). Space is O(n) for the two stacks, bounded by the number of pushed values.

Q: How do I identify that Min Stack requires the Stack pattern?

In technical interviews, look for key problem signals: Stack with O(1) minimum retrieval. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Stack strategy.

Q: What critical edge cases must be handled in Min Stack?

Essential edge cases to verify include: Repeated minimum values — mins must store duplicates, e.g. push 5, 3, 3 keeps [5, 3, 3]; Push after pop — mins stays in sync because both stacks are popped together; getMin on a fresh stack — the problem guarantees no top/getMin on an empty stack. Always walk through these scenarios with your interviewer before coding.

Q: Which tech companies frequently ask Min Stack?

Min Stack is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Bloomberg, Google.

Approach Summary

Maintain two stacks: main stack and min stack. Push to min stack only when new value <= current minimum.

Practice Mode

Solve it yourself before revealing the code

DSA interviews test reasoning from brute force to optimal. Think through the constraints first.

Full Solution & Approach

The trick is to answer getMin in O(1) without scanning the whole stack. Maintain a second stack, mins, that tracks the running minimum. On push(val): push val onto the main stack, and onto mins push min(val, current top of mins). Because mins stores the minimum at every prefix of the stack, its top is always the global minimum. On pop: pop both stacks in sync. top returns the main stack's top and getMin returns mins' top. The two stacks always have equal length, so they never desynchronize. Alternative formulations push (value, min_so_far) pairs onto a single stack, or push a sentinel whenever a new minimum arrives — the parallel-stack version is the most readable and equally valid.

Every operation does constant work — a push or pop plus an O(1) min comparison — so all four methods are O(1). Space is O(n) for the two stacks, bounded by the number of pushed values.

Solution Code

Solution

class MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();
    private Deque<Integer> mins = new ArrayDeque<>();

    public void push(int val) {
        stack.push(val);
        mins.push(mins.isEmpty() ? val : Math.min(val, mins.peek()));
    }

    public void pop() {
        stack.pop();
        mins.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return mins.peek();
    }
}

class MinStack {
    vector<int> stack;
    vector<int> mins;
public:
    void push(int val) {
        stack.push_back(val);
        mins.push_back(mins.empty() ? val : min(val, mins.back()));
    }
    void pop() {
        stack.pop_back();
        mins.pop_back();
    }
    int top() {
        return stack.back();
    }
    int getMin() {
        return mins.back();
    }
};

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

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

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

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

    def get_min(self) -> int:
        return self.mins[-1]

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

Edge Cases to Watch

Repeated minimum values — mins must store duplicates, e.g. push 5, 3, 3 keeps [5, 3, 3]
Push after pop — mins stays in sync because both stacks are popped together
getMin on a fresh stack — the problem guarantees no top/getMin on an empty stack

Algorithmic Pattern

Master the Stack Pattern

View Pattern Guide →

Study the core invariant, step-by-step decision framework, and common interview traps for the Stack pattern.

Framework: Stack • Interview Prep: Tested at FAANG • Explore all Stack problems & invariants →

How to Recognize This Pattern

Stack with O(1) minimum retrieval

Complexity Analysis

Time Complexity

O(1) all ops

Space Complexity

O(n)

Frequently Asked Questions

What is the optimal time and space complexity for Min Stack?

The optimal solution for Min Stack achieves O(1) all ops runtime complexity and requires O(n) auxiliary space. Every operation does constant work — a push or pop plus an O(1) min comparison — so all four methods are O(1). Space is O(n) for the two stacks, bounded by the number of pushed values.

How do I identify that Min Stack requires the Stack pattern?

In technical interviews, look for key problem signals: Stack with O(1) minimum retrieval. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Stack strategy.

What critical edge cases must be handled in Min Stack?

Essential edge cases to verify include: Repeated minimum values — mins must store duplicates, e.g. push 5, 3, 3 keeps [5, 3, 3]; Push after pop — mins stays in sync because both stacks are popped together; getMin on a fresh stack — the problem guarantees no top/getMin on an empty stack. Always walk through these scenarios with your interviewer before coding.

Which tech companies frequently ask Min Stack?