Min Stack

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

Language Selection

Choose your preferred programming language

Showing: Python

Min Stack

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.

Input/Output Specifications

Input: Sequence of operations with their parameters
Output: Results of operations (for top() and getMin())
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

Examples

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

Example 2:

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

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

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

Solution Approaches

Approach 1: Two Stacks (Optimal)

Use two stacks: one for the actual data and another to keep track of minimum values.

Algorithm Explanation

Data Stack: Normal stack operations for push/pop/top
Min Stack: Tracks minimum values at each level
Push: Add to data stack, and add to min stack if it’s <= current minimum
Pop: Remove from data stack, and remove from min stack if it matches current minimum
GetMin: Return top of min stack

Implementation

Python:

class MinStack:
    """
    Two stacks approach for Min Stack
    All operations: O(1) time
    Space: O(n) where n is number of elements
    """
    
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, val: int) -> None:
        """Push element onto stack"""
        self.stack.append(val)
        # Push to min_stack if it's empty or val is <= current minimum
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
    
    def pop(self) -> None:
        """Remove element from top of stack"""
        if self.stack:
            val = self.stack.pop()
            # Remove from min_stack if it matches the minimum
            if self.min_stack and val == self.min_stack[-1]:
                self.min_stack.pop()
    
    def top(self) -> int:
        """Get top element of stack"""
        return self.stack[-1] if self.stack else -1
    
    def getMin(self) -> int:
        """Get minimum element in O(1) time"""
        return self.min_stack[-1] if self.min_stack else -1

Java:

class MinStack {
    /**
     * Two stacks approach for Min Stack
     * All operations: O(1) time
     * Space: O(n) where n is number of elements
     */
    
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        // Push to minStack if it's empty or val is <= current minimum
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        if (!stack.isEmpty()) {
            int val = stack.pop();
            // Remove from minStack if it matches the minimum
            if (!minStack.isEmpty() && val == minStack.peek()) {
                minStack.pop();
            }
        }
    }
    
    public int top() {
        return stack.isEmpty() ? -1 : stack.peek();
    }
    
    public int getMin() {
        return minStack.isEmpty() ? -1 : minStack.peek();
    }
}

Go:

// MinStack - Two stacks approach
// All operations: O(1) time
// Space: O(n) where n is number of elements
type MinStack struct {
    stack    []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{
        stack:    make([]int, 0),
        minStack: make([]int, 0),
    }
}

func (s *MinStack) Push(val int) {
    s.stack = append(s.stack, val)
    // Push to minStack if it's empty or val is <= current minimum
    if len(s.minStack) == 0 || val <= s.minStack[len(s.minStack)-1] {
        s.minStack = append(s.minStack, val)
    }
}

func (s *MinStack) Pop() {
    if len(s.stack) > 0 {
        val := s.stack[len(s.stack)-1]
        s.stack = s.stack[:len(s.stack)-1]
        // Remove from minStack if it matches the minimum
        if len(s.minStack) > 0 && val == s.minStack[len(s.minStack)-1] {
            s.minStack = s.minStack[:len(s.minStack)-1]
        }
    }
}

func (s *MinStack) Top() int {
    if len(s.stack) == 0 {
        return -1
    }
    return s.stack[len(s.stack)-1]
}

func (s *MinStack) GetMin() int {
    if len(s.minStack) == 0 {
        return -1
    }
    return s.minStack[len(s.minStack)-1]
}

JavaScript:

/**
 * Two stacks approach for Min Stack
 * All operations: O(1) time
 * Space: O(n) where n is number of elements
 */
class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];
    }
    
    push(val) {
        this.stack.push(val);
        // Push to minStack if it's empty or val is <= current minimum
        if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(val);
        }
    }
    
    pop() {
        if (this.stack.length > 0) {
            const val = this.stack.pop();
            // Remove from minStack if it matches the minimum
            if (this.minStack.length > 0 && val === this.minStack[this.minStack.length - 1]) {
                this.minStack.pop();
            }
        }
    }
    
    top() {
        return this.stack.length > 0 ? this.stack[this.stack.length - 1] : -1;
    }
    
    getMin() {
        return this.minStack.length > 0 ? this.minStack[this.minStack.length - 1] : -1;
    }
}

C#:

public class MinStack {
    /// <summary>
    /// Two stacks approach for Min Stack
    /// All operations: O(1) time
    /// Space: O(n) where n is number of elements
    /// </summary>
    
    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);
        // Push to minStack if it's empty or val is <= current minimum
        if (minStack.Count == 0 || val <= minStack.Peek()) {
            minStack.Push(val);
        }
    }
    
    public void Pop() {
        if (stack.Count > 0) {
            int val = stack.Pop();
            // Remove from minStack if it matches the minimum
            if (minStack.Count > 0 && val == minStack.Peek()) {
                minStack.Pop();
            }
        }
    }
    
    public int Top() {
        return stack.Count > 0 ? stack.Peek() : -1;
    }
    
    public int GetMin() {
        return minStack.Count > 0 ? minStack.Peek() : -1;
    }
}

Approach 2: Single Stack with Node Pairs

Store pairs of (value, minimum_so_far) in a single stack.

Python:

class MinStackSingle:
    """
    Single stack with pairs approach
    All operations: O(1) time
    Space: O(n) where n is number of elements
    """
    
    def __init__(self):
        self.stack = []  # Store (value, min_so_far) pairs
    
    def push(self, val: int) -> None:
        if not self.stack:
            min_so_far = val
        else:
            min_so_far = min(val, self.stack[-1][1])
        self.stack.append((val, min_so_far))
    
    def pop(self) -> None:
        if self.stack:
            self.stack.pop()
    
    def top(self) -> int:
        return self.stack[-1][0] if self.stack else -1
    
    def getMin(self) -> int:
        return self.stack[-1][1] if self.stack else -1

Approach 3: Space-Optimized Single Stack

Use mathematical approach to store difference from minimum.

Python:

class MinStackOptimized:
    """
    Space-optimized approach using differences
    All operations: O(1) time
    Space: O(n) but more space-efficient
    """
    
    def __init__(self):
        self.stack = []
        self.min_val = None
    
    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min_val = val
        else:
            # Store difference from current minimum
            diff = val - self.min_val
            self.stack.append(diff)
            # Update minimum if current value is smaller
            if val < self.min_val:
                self.min_val = val
    
    def pop(self) -> None:
        if self.stack:
            diff = self.stack.pop()
            # If difference is negative, we popped the minimum
            if diff < 0:
                self.min_val = self.min_val - diff
    
    def top(self) -> int:
        if not self.stack:
            return -1
        diff = self.stack[-1]
        if diff < 0:
            return self.min_val
        else:
            return self.min_val + diff
    
    def getMin(self) -> int:
        return self.min_val if self.min_val is not None else -1

Complexity Analysis

Two Stacks Approach

Time Complexity: O(1) for all operations
Space Complexity: O(n) where n is the number of elements (worst case: all elements are minimum)

Single Stack with Pairs

Time Complexity: O(1) for all operations
Space Complexity: O(n) always stores 2n values

Space-Optimized Approach

Time Complexity: O(1) for all operations
Space Complexity: O(n) but more space-efficient in practice

Key Insights

Auxiliary Data Structure: Need additional space to track minimum efficiently
Minimum Tracking: Only push to min stack when value <= current minimum
Synchronization: Keep data and min stacks synchronized during pop operations
Edge Cases: Handle duplicate minimum values correctly

Edge Cases

Empty Stack: All operations on empty stack
Single Element: Push one element, then getMin
Duplicate Minimums: Multiple elements with same minimum value
Decreasing Sequence: All elements are new minimums
Increasing Sequence: Only first element is minimum

Test Cases

# Test cases for validation
def test_min_stack():
    min_stack = MinStack()
    
    # Test single element
    min_stack.push(5)
    assert min_stack.getMin() == 5
    assert min_stack.top() == 5
    
    # Test decreasing sequence (all minimums)
    min_stack.push(3)
    min_stack.push(1)
    assert min_stack.getMin() == 1
    
    # Test pop removes minimum
    min_stack.pop()  # Remove 1
    assert min_stack.getMin() == 3
    assert min_stack.top() == 3
    
    # Test duplicate minimums
    min_stack.push(1)
    min_stack.push(1)
    assert min_stack.getMin() == 1
    min_stack.pop()
    assert min_stack.getMin() == 1  # Still 1

Follow-up Questions

Max Stack: Implement a stack that also supports getMax() in O(1)
Min Stack with Increment: Support incrementing bottom k elements
Frequency Stack: Track element frequencies while maintaining stack operations
Min Stack in O(1) Space: Can we do better than O(n) auxiliary space?

Common Mistakes

Not Handling Duplicates: Forgetting that multiple elements can have the same minimum value
Incorrect Pop Logic: Not checking if popped element equals current minimum
Edge Case Handling: Not handling empty stack scenarios properly
Synchronization Issues: Min stack getting out of sync with data stack

Interview Tips

Start with Clarification: Ask about duplicate values and empty stack behavior
Explain Trade-offs: Discuss space vs time complexity trade-offs
Walk Through Example: Trace through operations step by step
Handle Edge Cases: Always consider empty stack and single element cases
Optimize Incrementally: Start with basic solution, then optimize
Code Clean Solution: Focus on the two-stacks approach first as it’s most intuitive