Leetcode - 155. Min Stack

Medium

Dec 22, 2025

#stack

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

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.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

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

-231 <= val <= 231 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 104 calls will be made to push, pop, top, and getMin.

Constraints:

Notes

Intuition

To support O(1) minimum retrieval, we need to track minimums as they change. A second stack that only stores values when they become the new minimum (or equal to it) maintains this information.

Implementation

Maintain two stacks: the main stack and a min stack. On push, always add to the main stack; if the value is less than or equal to the current minimum (or min stack is empty), also push to min stack. On pop, if the popped value equals the min stack top, pop from min stack too. getMin returns the top of min stack. top returns the main stack top.

Edge-cases

Push to min stack when value equals the current min (not just less than) to handle duplicate minimums correctly.

Time: O(1) — all operations are constant time
Space: O(n) — both stacks can grow to n elements

Complexity

Solution

class MinStack:

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

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

        if val <= self.getMin() or not self.min_stack:
            self.min_stack.append(val)
        

    def pop(self) -> None:
        if self.min_stack and self.min_stack[-1] == self.stack[-1]:
            self.min_stack.pop()
        self.stack.pop()
        

    def top(self) -> int:
        return self.stack[-1] # will always be called on non-empty stack
        

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


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    obj = MinStack()