LeetEye LeetEye
Medium Stack ~5 min

Min Stack

stack min-stack

Problem

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

All operations must be O(1) time.

Examples

Example 1
Input: nums = [1,2,3]
Output: result
Key Insight

Track the minimum at each "level" of the stack.

Track 'minimum so far' at each stack position — either with pairs (val, min) or synchronized min stack.

How to Approach This Problem

Pattern Recognition: When you see keywords like min stack stack, think Stack.

Step-by-Step Reasoning

1 If we store just the minimum value, what breaks on pop?
Answer: We lose what the previous minimum was
If we pop the current min, we don't know the second smallest without scanning.
2 When element X is on top, the minimum is determined by:
Answer: All elements currently in the stack
Minimum is among current elements. When X is popped, min changes to min of remaining elements.
3 At each stack position, we can precompute:
Answer: The minimum of all elements at or below this position
This "minimum-so-far" lets us answer getMin() instantly and recover previous min on pop.
4 Which approach works for O(1) operations?
Answer: Both A and B work
Pairs and synchronized stacks are equivalent. Both achieve O(1) for all operations.
5 With two stacks (main, mins), when pushing value X:
Answer: Push X to main; push min(X, mins.top()) to mins
Main stack holds all values. Mins stack holds the minimum at each level. They stay synchronized in size.

Solution

class MinStack:
    def __init__(self):
        self.stack = []      # (value, min_so_far)
    
    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            current_min = min(val, self.stack[-1][1])
            self.stack.append((val, current_min))
    
    def pop(self) -> None:
        self.stack.pop()
    
    def top(self) -> int:
        return self.stack[-1][0]
    
    def getMin(self) -> int:
        return self.stack[-1][1]

Complexity Analysis

Time O(1)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Stack problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye