ToolMight LogoToolMight
MediumStackPattern: Auxiliary Min TrackingPattern: Design

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant O(1) time. The premier problem for learning how to augment linear data structures with auxiliary state.

Problem Statement

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.

Examples & Constraints

Example 1
Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]\n[[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Explanation: minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3\nminStack.pop(); minStack.top(); // return 0\nminStack.getMin(); // return -2
Constraints
  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

Paired Auxiliary Min Stack

Optimal Approach
Time:O(1) for all operations
Space:O(n)

Maintain two parallel stacks: a primary data stack and an auxiliary min stack that records the running minimum value associated with each stack depth in O(1) time.

Time ComplexityO(1) for all operations

push, pop, top, and getMin all execute in constant O(1) time without any loops or traversals.

Space ComplexityO(n)

Consumes 2N space to store N primary elements and N associated running minimums.

Underlying algorithmic logic

The Invariant: Every Stack Level Remembers Its Minimum

A normal stack easily provides O(1) push, pop, and top. The challenge is getMin():

  • Scanning the stack takes O(n) time.
  • If we only keep a single global variable currentMin, when that minimum is popped off, we cannot know what the previous minimum was without scanning the entire remaining stack!

The Solution: History Tracking

Because stack operations strictly adhere to Last-In, First-Out (LIFO) ordering, the minimum of any prefix of the stack never changes as long as those elements remain in the stack!

  1. Maintain two stacks:
  • dataStack: Stores normal values.
  • minStack: Stores the running minimum up to the current height.
  1. Push(val):
  • Push val onto dataStack.
  • The new minimum is min(val, minStack.top()) (or val if minStack is empty).
  • Push this new minimum onto minStack.
  1. Pop():
  • Pop simultaneously from both dataStack and minStack.
  • The previous minimum is naturally restored at the top of minStack!
  1. Top(): Return dataStack.top().
  2. GetMin(): Return minStack.top() in instant O(1) time.

Step-by-step execution walkthrough

1
push(-2)

dataStack: [-2], minStack: [-2]. Current min = -2.

data: [-2], min: [-2]
2
push(0)

dataStack: [-2, 0]. min(-2, 0) is -2. minStack: [-2, -2].

data: [-2, 0], min: [-2, -2]
3
push(-3)

dataStack: [-2, 0, -3]. min(-2, -3) is -3. minStack: [-2, -2, -3].

getMin() -> top of minStack = -3
4
pop()

Pop both stacks. -3 is removed. Top of minStack restores to -2!

data: [-2, 0], min: [-2, -2] -> getMin() is -2
Advantages
  • •Guaranteed constant O(1) time for every operation
  • •Simple and robust to implement
Trade-offs
  • •Doubles memory overhead by allocating two elements per entry

Code Implementations

Copy & paste production-ready solutions for Paired Auxiliary Min Stack in your language of choice

File: solution.py
Python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        else:
            self.min_stack.append(self.min_stack[-1])
    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()
    def top(self) -> int:
        return self.stack[-1]
    def get_min(self) -> int:
        return self.min_stack[-1]
if __name__ == "__main__":
    ms = MinStack()
    ms.push(-2)
    ms.push(0)
    ms.push(-3)
    print("Min:", ms.get_min())  # -3
    ms.pop()
    print("Top:", ms.top())      # 0
    print("Min:", ms.get_min())  # -2
Interactive visualizer available

Understand Stack Visually

Learn the Last-In, First-Out (LIFO) stack data structure with pushing, popping, and structural queries. Test live edge cases and watch memory state transitions step-by-step.

Launch Stack Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyStack
Visualizer

Valid Parentheses

Verify that code brackets (), {}, and [] are properly closed and nested in order. This is the exact algorithm compilers, linters, and IDEs use to detect syntax errors in real-time.

1 approach(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic