155. Min Stack - Explanation

Description

Design a stack class that supports the push, pop, top, and getMin operations.

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

Each function should run in $O(1)$ time.

Example 1:

Input: ["MinStack", "push", 1, "push", 2, "push", 0, "getMin", "pop", "top", "getMin"]

Output: [null,null,null,null,0,null,2,1]

Explanation:
MinStack minStack = new MinStack();
minStack.push(1);
minStack.push(2);
minStack.push(0);
minStack.getMin(); // return 0
minStack.pop();
minStack.top();    // return 2
minStack.getMin(); // return 1

Constraints:

-2^31 <= val <= 2^31 - 1.
pop, top and getMin will always be called on non-empty stacks.

Topics

Stack Design

Recommended Time & Space Complexity

You should aim for a solution with O(1) time for each function call and O(n) space, where n is the maximum number of elements present in the stack.

Hint 1

A brute force solution would be to always check for the minimum element in the stack for the getMin() function call. This would be an O(n) approach. Can you think of a better way? Maybe O(n) extra space to store some information.

Hint 2

We can use a stack to maintain the elements. But how can we find the minimum element at any given time? Perhaps we should consider a prefix approach.

Hint 3

We use an additional stack to maintain the prefix minimum element. When popping elements from the main stack, we should also pop from this extra stack. However, when pushing onto the extra stack, we should push the minimum of the top element of the extra stack and the current element onto this extra stack.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Stack Data Structure - Understanding LIFO (Last In First Out) operations including push, pop, and peek
Auxiliary Data Structures - Using additional stacks or variables to track extra state alongside the main data structure
Space-Time Tradeoffs - Trading extra memory for faster operations (e.g., O(n) space for O(1) getMin)

1. Brute Force

Intuition

To get the minimum value, this approach simply looks through all elements in the stack.
Since a normal stack does not store any extra information about the minimum, the only way to find it is to temporarily remove every element, track the smallest one, and then put everything back.
It's easy to understand but slow because each getMin call scans the entire stack.

Algorithm

To push a value, append it to the stack.
To pop, remove the top element of the stack.
To top, return the last element.
To getMin:
- Create a temporary list.
- Pop all elements from the stack while tracking the smallest value.
- Push all elements back from the temporary list to restore the stack.
- Return the smallest value found.

class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

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

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

    def getMin(self) -> int:
        tmp = []
        mini = self.stack[-1]

        while len(self.stack):
            mini = min(mini, self.stack[-1])
            tmp.append(self.stack.pop())

        while len(tmp):
            self.stack.append(tmp.pop())

        return mini

class MinStack {

    private Stack<Integer> stack;

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
    }

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

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

    public int getMin() {
        Stack<Integer> tmp = new Stack<>();
        int mini = stack.peek();

        while (!stack.isEmpty()) {
            mini = Math.min(mini, stack.peek());
            tmp.push(stack.pop());
        }

        while (!tmp.isEmpty()) {
            stack.push(tmp.pop());
        }

        return mini;
    }
}

class MinStack {
public:
    stack<int> stk;
    MinStack() {

    }

    void push(int val) {
        stk.push(val);
    }

    void pop() {
        stk.pop();
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        stack<int> tmp;
        int mini = stk.top();
        while (stk.size()) {
            mini = min(mini, stk.top());
            tmp.push(stk.top());
            stk.pop();
        }

        while (tmp.size()) {
            stk.push(tmp.top());
            tmp.pop();
        }

        return mini;
    }
};

class MinStack {
    constructor() {
        this.stack = [];
    }

    /**
     * @param {number} val
     * @return {void}
     */
    push(val) {
        this.stack.push(val);
    }

    /**
     * @return {void}
     */
    pop() {
        this.stack.pop();
    }

    /**
     * @return {number}
     */
    top() {
        return this.stack[this.stack.length - 1];
    }

    /**
     * @return {number}
     */
    getMin() {
        const tmp = [];
        let mini = this.stack[this.stack.length - 1];

        while (this.stack.length > 0) {
            mini = Math.min(mini, this.stack[this.stack.length - 1]);
            tmp.push(this.stack.pop());
        }

        while (tmp.length > 0) {
            this.stack.push(tmp.pop());
        }

        return mini;
    }
}

public class MinStack {
    private Stack<int> stack;

    public MinStack() {
        stack = new Stack<int>();
    }

    public void Push(int val) {
        stack.Push(val);
    }

    public void Pop() {
        stack.Pop();
    }

    public int Top() {
        return stack.Peek();
    }

    public int GetMin() {
        Stack<int> tmp = new Stack<int>();
        int mini = stack.Peek();

        while (stack.Count > 0) {
            mini = System.Math.Min(mini, stack.Peek());
            tmp.Push(stack.Pop());
        }

        while (tmp.Count > 0) {
            stack.Push(tmp.Pop());
        }

        return mini;
    }
}

type MinStack struct {
    stack *linkedliststack.Stack
}

func Constructor() MinStack {
    return MinStack{stack: linkedliststack.New()}
}

func (this *MinStack) Push(val int) {
    this.stack.Push(val)
}

func (this *MinStack) Pop() {
    this.stack.Pop()
}

func (this *MinStack) Top() int {
    top, _ := this.stack.Peek()
    return top.(int)
}

func (this *MinStack) GetMin() int {
    tmp := linkedliststack.New()
    min := this.Top()

    for !this.stack.Empty() {
        val, _ := this.stack.Pop()
        min = getMin(min, val.(int))
        tmp.Push(val)
    }

    for !tmp.Empty() {
        val, _ := tmp.Pop()
        this.stack.Push(val)
    }

    return min
}

func getMin(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class MinStack() {
    private val stack = ArrayDeque<Int>()

    fun push(`val`: Int) {
        stack.addLast(`val`)
    }

    fun pop() {
        stack.removeLast()
    }

    fun top(): Int {
        return stack.last()
    }

    fun getMin(): Int {
        val tmp = ArrayDeque<Int>()
        var min = stack.last()

        while (stack.isNotEmpty()) {
            min = minOf(min, stack.last())
            tmp.addLast(stack.removeLast())
        }

        while (tmp.isNotEmpty()) {
            stack.addLast(tmp.removeLast())
        }

        return min
    }
}

class MinStack {
    private var stack: [Int] = []

    init() {}

    func push(_ val: Int) {
        stack.append(val)
    }

    func pop() {
        stack.popLast()
    }

    func top() -> Int {
        return stack.last!
    }

    func getMin() -> Int {
        var tmp = [Int]()
        var mini = stack.last!

        while !stack.isEmpty {
            mini = min(mini, stack.last!)
            tmp.append(stack.removeLast())
        }

        while !tmp.isEmpty {
            stack.append(tmp.removeLast())
        }

        return mini
    }
}

Time & Space Complexity

Time complexity: $O(n)$ for $getMin()$ and $O(1)$ for other operations.
Space complexity: $O(n)$ for $getMin()$ and $O(1)$ for other operations.

2. Two Stacks

Intuition

Instead of searching the whole stack to find the minimum every time, we can keep a second stack that always stores the minimum value up to that point.
So whenever we push a new value, we compare it with the current minimum and store the smaller one on the minStack.
This guarantees that the top of minStack is always the minimum of the entire stack — allowing getMin() to work in constant time.

Algorithm

Maintain two stacks:
- stack → stores all pushed values.
- minStack → stores the minimum so far at each level.
On push(val):
- Push val onto stack.
- Compute the new minimum (between val and the current minimum on minStack).
- Push this minimum onto minStack.
On pop():
- Pop from both stack and minStack to keep them aligned.
On top():
- Return the top of stack.
On getMin():
- Return the top of minStack, which is the current minimum.

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

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

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

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

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

public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.isEmpty()) return;
        int top = stack.pop();
        if (top == minStack.peek()) {
            minStack.pop();
        }
    }

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

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

class MinStack {
private:
    std::stack<int> stack;
    std::stack<int> minStack;

public:
    MinStack() {}

    void push(int val) {
        stack.push(val);
        val = std::min(val, minStack.empty() ? val : minStack.top());
        minStack.push(val);
    }

    void pop() {
        stack.pop();
        minStack.pop();
    }

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

    int getMin() {
        return minStack.top();
    }
};

class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];
    }

    /**
     * @param {number} val
     * @return {void}
     */
    push(val) {
        this.stack.push(val);
        val = Math.min(
            val,
            this.minStack.length === 0
                ? val
                : this.minStack[this.minStack.length - 1],
        );
        this.minStack.push(val);
    }

    /**
     * @return {void}
     */
    pop() {
        this.stack.pop();
        this.minStack.pop();
    }

    /**
     * @return {number}
     */
    top() {
        return this.stack[this.stack.length - 1];
    }

    /**
     * @return {number}
     */
    getMin() {
        return this.minStack[this.minStack.length - 1];
    }
}

public class MinStack {

    private Stack<int> stack;
    private Stack<int> minStack;

    public MinStack() {
        stack = new Stack<int>();
        minStack = new Stack<int>();
    }

    public void Push(int val) {
        stack.Push(val);
        val = Math.Min(val, minStack.Count == 0 ? val : minStack.Peek());
        minStack.Push(val);
    }

    public void Pop() {
        stack.Pop();
        minStack.Pop();
    }

    public int Top() {
        return stack.Peek();
    }

    public int GetMin() {
        return minStack.Peek();
    }
}

type MinStack struct {
    stack    *linkedliststack.Stack
    minStack *linkedliststack.Stack
}

func Constructor() MinStack {
    return MinStack{
        stack:    linkedliststack.New(),
        minStack: linkedliststack.New(),
    }
}

func (this *MinStack) Push(val int) {
    this.stack.Push(val)
    minVal := val
    if !this.minStack.Empty() {
        if top, ok := this.minStack.Peek(); ok {
            if top.(int) < val {
                minVal = top.(int)
            }
        }
    }
    this.minStack.Push(minVal)
}

func (this *MinStack) Pop() {
    this.stack.Pop()
    this.minStack.Pop()
}

func (this *MinStack) Top() int {
    top, _ := this.stack.Peek()
    return top.(int)
}

func (this *MinStack) GetMin() int {
    min, _ := this.minStack.Peek()
    return min.(int)
}

class MinStack() {
    private val stack = ArrayDeque<Int>()
    private val minStack = ArrayDeque<Int>()

    fun push(`val`: Int) {
        stack.addLast(`val`)
        val minVal = if (minStack.isNotEmpty()) minOf(`val`, minStack.last()) else `val`
        minStack.addLast(minVal)
    }

    fun pop() {
        stack.removeLast()
        minStack.removeLast()
    }

    fun top(): Int {
        return stack.last()
    }

    fun getMin(): Int {
        return minStack.last()
    }
}

class MinStack {
    private var stack: [Int] = []
    private var minStack: [Int] = []

    init() {}

    func push(_ val: Int) {
        stack.append(val)
        let minVal = min(val, minStack.last ?? val)
        minStack.append(minVal)
    }

    func pop() {
        stack.popLast()
        minStack.popLast()
    }

    func top() -> Int {
        return stack.last!
    }

    func getMin() -> Int {
        return minStack.last!
    }
}

Time & Space Complexity

Time complexity: $O(1)$ for all operations.
Space complexity: $O(n)$

3. One Stack

Intuition

This approach keeps only one stack and stores encoded values instead of the actual numbers.
The trick is to record the difference between the pushed value and the current minimum.
Whenever a new minimum is pushed, we store a negative encoded value, which signals that the minimum has changed.
Later, when popping such a value, we can decode it to restore the previous minimum.

This way, the stack internally keeps track of all minimum updates without needing a second stack — giving constant-time operations with minimal space.

Algorithm

Maintain:
- stack → stores encoded values (not the actual numbers)
- min → stores the current minimum in the stack
Push(val):
- If the stack is empty:
  - Push 0 (difference) and set min = val.
- Otherwise:
  - Push val - min.
  - If val is the new minimum, update min.
Pop():
- Pop the encoded value.
- If this value is negative, it means the popped element was the minimum.
  - Restore the previous minimum using the encoded difference.
Top():
- If the encoded value is positive, return encoded + min.
- If it's negative, the top actual value is simply min.
getMin():
- Return the current min.

class MinStack:
    def __init__(self):
        self.min = float('inf')
        self.stack = []

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min = val
        else:
            self.stack.append(val - self.min)
            if val < self.min:
                self.min = val

    def pop(self) -> None:
        if not self.stack:
            return

        pop = self.stack.pop()

        if pop < 0:
            self.min = self.min - pop

    def top(self) -> int:
        top = self.stack[-1]
        if top > 0:
            return top + self.min
        else:
            return self.min

    def getMin(self) -> int:
        return self.min

public class MinStack {
    long min;
    Stack<Long> stack;

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = val;
        } else {
            stack.push(val - min);
            if (val < min) min = val;
        }
    }

    public void pop() {
        if (stack.isEmpty()) return;

        long pop = stack.pop();

        if (pop < 0) min = min - pop;
    }

    public int top() {
        long top = stack.peek();
        if (top > 0) {
            return (int) (top + min);
        } else {
            return (int) min;
        }
    }

    public int getMin() {
        return (int) min;
    }
}

class MinStack {
private:
    long min;
    std::stack<long> stack;

public:
    MinStack() {}

    void push(int val) {
        if (stack.empty()) {
            stack.push(0);
            min = val;
        } else {
            stack.push(val - min);
            if (val < min) min = val;
        }
    }

    void pop() {
        if (stack.empty()) return;

        long pop = stack.top();
        stack.pop();

        if (pop < 0) min = min - pop;
    }

    int top() {
        long top = stack.top();
        return (top > 0) ? (top + min) : (int)min;
    }

    int getMin() {
        return (int)min;
    }
};

class MinStack {
    constructor() {
        this.min = Infinity;
        this.stack = [];
    }

    /**
     * @param {number} val
     * @return {void}
     */
    push(val) {
        if (this.stack.length === 0) {
            this.stack.push(0);
            this.min = val;
        } else {
            this.stack.push(val - this.min);
            if (val < this.min) this.min = val;
        }
    }

    /**
     * @return {void}
     */
    pop() {
        if (this.stack.length === 0) return;

        const pop = this.stack.pop();

        if (pop < 0) this.min -= pop;
    }

    /**
     * @return {number}
     */
    top() {
        const top = this.stack[this.stack.length - 1];
        return top > 0 ? top + this.min : this.min;
    }

    /**
     * @return {number}
     */
    getMin() {
        return this.min;
    }
}

public class MinStack {
    private long min;
    private Stack<long> stack;

    public MinStack() {
        stack = new Stack<long>();
    }

    public void Push(int val) {
        if (stack.Count == 0) {
            stack.Push(0L);
            min = val;
        } else {
            stack.Push(val - min);
            if (val < min) min = val;
        }
    }

    public void Pop() {
        if (stack.Count == 0) return;

        long pop = stack.Pop();

        if (pop < 0) min -= pop;
    }

    public int Top() {
        long top = stack.Peek();
        return top > 0 ? (int)(top + min) : (int)(min);
    }

    public int GetMin() {
        return (int)min;
    }
}

type MinStack struct {
    min   int
    stack []int
}

func Constructor() MinStack {
    return MinStack{
        min:   math.MaxInt64,
        stack: []int{},
    }
}

func (this *MinStack) Push(val int) {
    if len(this.stack) == 0 {
        this.stack = append(this.stack, 0)
        this.min = val
    } else {
        this.stack = append(this.stack, val - this.min)
        if val < this.min {
            this.min = val
        }
    }
}

func (this *MinStack) Pop() {
    if len(this.stack) == 0 {
        return
    }
    pop := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    if pop < 0 {
        this.min = this.min - pop
    }
}

func (this *MinStack) Top() int {
    top := this.stack[len(this.stack)-1]
    if top > 0 {
        return top + this.min
    }
    return this.min
}

func (this *MinStack) GetMin() int {
    return this.min
}

class MinStack() {
    private var min: Long = Long.MAX_VALUE
    private val stack = ArrayDeque<Long>()

    fun push(`val`: Int) {
        val valAsLong = `val`.toLong()
        if (stack.isEmpty()) {
            stack.addLast(0L)
            min = valAsLong
        } else {
            stack.addLast(valAsLong - min)
            if (valAsLong < min) {
                min = valAsLong
            }
        }
    }

    fun pop() {
        if (stack.isEmpty()) return
        val pop = stack.removeLast()
        if (pop < 0) {
            min -= pop
        }
    }

    fun top(): Int {
        val top = stack.last()
        return if (top > 0) (top + min).toInt() else min.toInt()
    }

    fun getMin(): Int {
        return min.toInt()
    }
}

class MinStack {
    private var minVal: Int = Int.max
    private var stack: [Int] = []

    init() {}

    func push(_ val: Int) {
        if stack.isEmpty {
            stack.append(0)
            minVal = val
        } else {
            stack.append(val - minVal)
            if val < minVal {
                minVal = val
            }
        }
    }

    func pop() {
        if stack.isEmpty {
            return
        }

        let pop = stack.removeLast()

        if pop < 0 {
            minVal -= pop
        }
    }

    func top() -> Int {
        let top = stack.last!
        return top > 0 ? top + minVal : minVal
    }

    func getMin() -> Int {
        return minVal
    }
}

Time & Space Complexity

Time complexity: $O(1)$ for all operations.
Space complexity: $O(n)$

Common Pitfalls

Not Synchronizing the Two Stacks

When using the two-stack approach, some implementations only push to minStack when the new value is smaller than the current minimum. This optimization requires careful handling during pop(): you must only pop from minStack when the popped value equals the current minimum. Forgetting this synchronization causes minStack to become misaligned with the main stack, returning incorrect minimums.

Integer Overflow in the Encoded Value Approach

The one-stack solution stores val - min as encoded values. When dealing with extreme integer values (e.g., Integer.MIN_VALUE and Integer.MAX_VALUE), this subtraction can overflow. Using long instead of int for the encoded values and the minimum prevents this issue in languages with fixed-width integers.