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.

Each operation must run in O(1) time.

What to notice first

• The stack must support all four operations in constant time.
• The key challenge is: how can we track the minimum without scanning the entire stack on every getMin() call?
• You cannot modify the values being pushed; you must design the data structure cleverly.
• Every push and pop must maintain the minimum invariant.

Examples

Operation	Stack	Min	Notes
push(-2)	[-2]	-2	Initialize with minimum as -2
push(0)	[-2, 0]	-2	New min is still -2
push(-3)	[-2, 0, -3]	-3	New min is -3
getMin()	[-2, 0, -3]	-3	Return -3 ✓
pop()	[-2, 0]	-2	Remove -3, min reverts to -2
top()	[-2, 0]	—	Return 0 ✓
getMin()	[-2, 0]	-2	Return -2 ✓

Constraints

• -2^31 <= val <= 2^31 - 1
• 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.

Real-World Applications

Where this pattern appears

• Stock price tracking — maintain running minimum price alongside incoming prices during trading sessions.
• Browser history navigation — track the minimum (or maximum) time spent on each visited page.
• Network latency monitoring — retrieve minimum latency within a sliding time window as packets arrive.
• Undo/redo systems — maintain a minimum or maximum state value as operations are pushed and popped.
• Expression evaluation — some parsing tasks need to track minimum depth or priority level as tokens arrive.

Complexity Comparison

Approach	Time	Space	Additional Memory	Best When
Dual Stack	O(1) all ops	O(n)	O(n) for min stack	Clearer logic, easier to debug
Single Stack with Pairs	O(1) all ops	O(n)	O(n) same stack	Memory-conscious, stores both in one place

Which approach should you learn first?

• Pick Dual Stack if you want the simplest mental model: one stack for values, one for mins.
• Pick Single Stack with Pairs if you want to understand space optimization and tuple/pair handling.

Clearer Logic

Dual Stack

O(1) all ops · O(n) space

Space Optimized

Single Stack with Pairs

O(1) all ops · O(n) space

Approach 1: Dual Stack (Recommended)

★ Recommended

Maintain two stacks:

1. Main stack: stores all pushed values.
2. Min stack: stores the minimum value at each level (only pushes/pops in sync with main stack).

Whenever we push a value to the main stack, we push min(val, current_min) to the min stack. When we pop from the main stack, we pop from the min stack too. This way, getMin() is always O(1) by peeking the top of the min stack.

⏱ Time O(1) All operations constant 💾 Space O(n) Two stacks of size n

Step-by-step Example

Sequence of operations: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Step	Operation	Main Stack	Min Stack	Result	Action
1	push(-2)	[-2]	[-2]	—	First element: min is -2 itself
2	push(0)	[-2, 0]	[-2, -2]	—	min(-2, 0) = -2, so push -2
3	push(-3)	[-2, 0, -3]	[-2, -2, -3]	—	min(-2, -3) = -3, so push -3
4	getMin()	[-2, 0, -3]	[-2, -2, -3]	-3	Peek top of min stack → -3 ✓
5	pop()	[-2, 0]	[-2, -2]	—	Remove from both stacks
6	top()	[-2, 0]	[-2, -2]	0	Peek main stack → 0 ✓
7	getMin()	[-2, 0]	[-2, -2]	-2	Peek min stack → -2 ✓

Animated walkthrough

How the dual stack solution tracks the minimum

Watch both stacks grow and shrink as you push, pop, and query. The min stack always shows the minimum at each level.

Back Autoplay Next Reset

Step 1 of 8

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

class MinStack:
    minStack = {} // main stack for all values
    mainStack = {} // separate stack for minimums

    function push(val):
        mainStack.push(val)
        if minStack is empty:
            minStack.push(val)
        else:
            minStack.push(min(val, minStack.top()))

    function pop():
        mainStack.pop()
        minStack.pop()

    function top():
        return mainStack.top()

    function getMin():
        return minStack.top()

Solution Code

Python

min_stack_dual.py

class MinStack:
    """Min Stack using two stacks (dual stack approach).

    Maintains a main stack for all values and a separate min stack
    that tracks the minimum value at each level.

    Time: O(1) per operation
    Space: O(n)
    """

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

    def push(self, val: int) -> None:
        self.main_stack.append(val)
        # Push to min_stack the minimum of val and current min
        if not self.min_stack:
            self.min_stack.append(val)
        else:
            self.min_stack.append(min(val, self.min_stack[-1]))

    def pop(self) -> None:
        self.main_stack.pop()
        self.min_stack.pop()

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

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


# Example usage
stack = MinStack()
stack.push(-2)
stack.push(0)
stack.push(-3)
print(f"Min: {stack.getMin()}")  # -3
stack.pop()
print(f"Top: {stack.top()}")     # 0
print(f"Min: {stack.getMin()}")  # -2

C++

min_stack_dual.cpp

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

class MinStack {
private:
    stack<int> main_stack;
    stack<int> min_stack;

public:
    /**
     * Min Stack using two stacks (dual stack approach).
     *
     * Maintains a main stack for all values and a separate min stack
     * that tracks the minimum value at each level.
     *
     * Time: O(1) per operation
     * Space: O(n)
     */

    void push(int val) {
        main_stack.push(val);
        // Push to min_stack the minimum of val and current min
        if (min_stack.empty()) {
            min_stack.push(val);
        } else {
            min_stack.push(min(val, min_stack.top()));
        }
    }

    void pop() {
        main_stack.pop();
        min_stack.pop();
    }

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

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

int main() {
    MinStack stack;
    stack.push(-2);
    stack.push(0);
    stack.push(-3);
    cout << "Min: " << stack.getMin() << endl;  // -3
    stack.pop();
    cout << "Top: " << stack.top() << endl;     // 0
    cout << "Min: " << stack.getMin() << endl;  // -2
    return 0;
}

Java

min_stack_dual.java

import java.util.Stack;

public class MinStackDual {
    /**
     * Min Stack using two stacks (dual stack approach).
     *
     * Maintains a main stack for all values and a separate min stack
     * that tracks the minimum value at each level.
     *
     * Time: O(1) per operation
     * Space: O(n)
     */

    private Stack<Integer> mainStack;
    private Stack<Integer> minStack;

    public MinStackDual() {
        mainStack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        mainStack.push(val);
        // Push to minStack the minimum of val and current min
        if (minStack.isEmpty()) {
            minStack.push(val);
        } else {
            minStack.push(Math.min(val, minStack.peek()));
        }
    }

    public void pop() {
        mainStack.pop();
        minStack.pop();
    }

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

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

    public static void main(String[] args) {
        MinStackDual stack = new MinStackDual();
        stack.push(-2);
        stack.push(0);
        stack.push(-3);
        System.out.println("Min: " + stack.getMin());  // -3
        stack.pop();
        System.out.println("Top: " + stack.top());     // 0
        System.out.println("Min: " + stack.getMin());  // -2
    }
}

JavaScript

min_stack_dual.js

/**
 * Min Stack using two stacks (dual stack approach).
 *
 * Maintains a main stack for all values and a separate min stack
 * that tracks the minimum value at each level.
 *
 * Time: O(1) per operation
 * Space: O(n)
 */
class MinStack {
  constructor() {
    this.mainStack = [];
    this.minStack = [];
  }

  push(val) {
    this.mainStack.push(val);
    // Push to minStack the minimum of val and current min
    if (this.minStack.length === 0) {
      this.minStack.push(val);
    } else {
      this.minStack.push(Math.min(val, this.minStack[this.minStack.length - 1]));
    }
  }

  pop() {
    this.mainStack.pop();
    this.minStack.pop();
  }

  top() {
    return this.mainStack[this.mainStack.length - 1];
  }

  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

// Example usage
const stack = new MinStack();
stack.push(-2);
stack.push(0);
stack.push(-3);
console.log(`Min: ${stack.getMin()}`);  // -3
stack.pop();
console.log(`Top: ${stack.top()}`);     // 0
console.log(`Min: ${stack.getMin()}`);  // -2

Rust

min_stack_dual.rs

/**
 * Min Stack using two stacks (dual stack approach).
 *
 * Maintains a main stack for all values and a separate min stack
 * that tracks the minimum value at each level.
 *
 * Time: O(1) per operation
 * Space: O(n)
 */
struct MinStack {
    main_stack: Vec<i32>,
    min_stack: Vec<i32>,
}

impl MinStack {
    fn new() -> Self {
        MinStack {
            main_stack: Vec::new(),
            min_stack: Vec::new(),
        }
    }

    fn push(&mut self, val: i32) {
        self.main_stack.push(val);
        // Push to min_stack the minimum of val and current min
        if self.min_stack.is_empty() {
            self.min_stack.push(val);
        } else {
            let current_min = (*self.min_stack.last().unwrap()).min(val);
            self.min_stack.push(current_min);
        }
    }

    fn pop(&mut self) {
        self.main_stack.pop();
        self.min_stack.pop();
    }

    fn top(&self) -> i32 {
        *self.main_stack.last().unwrap()
    }

    fn get_min(&self) -> i32 {
        *self.min_stack.last().unwrap()
    }
}

fn main() {
    let mut stack = MinStack::new();
    stack.push(-2);
    stack.push(0);
    stack.push(-3);
    println!("Min: {}", stack.get_min());  // -3
    stack.pop();
    println!("Top: {}", stack.top());      // 0
    println!("Min: {}", stack.get_min());  // -2
}

Go

min_stack_dual.go

package main

import (
  "fmt"
)

/**
 * Min Stack using two stacks (dual stack approach).
 *
 * Maintains a main stack for all values and a separate min stack
 * that tracks the minimum value at each level.
 *
 * Time: O(1) per operation
 * Space: O(n)
 */
type MinStack struct {
  mainStack []int
  minStack  []int
}

func NewMinStack() *MinStack {
  return &MinStack{
    mainStack: []int{},
    minStack:  []int{},
  }
}

func (ms *MinStack) Push(val int) {
  ms.mainStack = append(ms.mainStack, val)
  // Push to minStack the minimum of val and current min
  if len(ms.minStack) == 0 {
    ms.minStack = append(ms.minStack, val)
  } else {
    min := val
    if ms.minStack[len(ms.minStack)-1] < val {
      min = ms.minStack[len(ms.minStack)-1]
    }
    ms.minStack = append(ms.minStack, min)
  }
}

func (ms *MinStack) Pop() {
  ms.mainStack = ms.mainStack[:len(ms.mainStack)-1]
  ms.minStack = ms.minStack[:len(ms.minStack)-1]
}

func (ms *MinStack) Top() int {
  return ms.mainStack[len(ms.mainStack)-1]
}

func (ms *MinStack) GetMin() int {
  return ms.minStack[len(ms.minStack)-1]
}

func main() {
  stack := NewMinStack()
  stack.Push(-2)
  stack.Push(0)
  stack.Push(-3)
  fmt.Printf("Min: %d\n", stack.GetMin()) // -3
  stack.Pop()
  fmt.Printf("Top: %d\n", stack.Top())    // 0
  fmt.Printf("Min: %d\n", stack.GetMin()) // -2
}

Approach 2: Single Stack with Pairs

🎯 Interview Favourite

Instead of maintaining two separate stacks, store one element per level as a pair (value, min_at_this_level).

Each pair holds:

• value: the actual value being pushed
• min_at_this_level: the minimum from the bottom of the stack up to and including this element

When you push a new value, compute its minimum as min(val, previous_min) and store the pair. This way, the entire history of minimums is embedded in the stack itself.

Memory efficiency

Both approaches use O(n) space overall, but the pair approach stores everything in one data structure, which can be slightly more cache-friendly. However, the dual stack approach is often clearer to reason about in interviews.

⏱ Time O(1) All operations constant 💾 Space O(n) Single stack with pairs

Step-by-step Example

Sequence of operations: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Step	Operation	Stack	Top Pair	Min	Action
1	push(-2)	[(-2, -2)]	(-2, -2)	-2	First: value=min=-2
2	push(0)	[(-2, -2), (0, -2)]	(0, -2)	-2	min(0, -2) = -2
3	push(-3)	[(-2, -2), (0, -2), (-3, -3)]	(-3, -3)	-3	min(-3, -2) = -3
4	getMin()	[(-2, -2), (0, -2), (-3, -3)]	(-3, -3)	-3	Return second element of top pair
5	pop()	[(-2, -2), (0, -2)]	(0, -2)	-2	Remove top pair
6	top()	[(-2, -2), (0, -2)]	(0, -2)	—	Return 0 (first element of top pair)
7	getMin()	[(-2, -2), (0, -2)]	(0, -2)	-2	Return second element of top pair

Pseudocode

class MinStack:
    stack = [] // stores (value, min_at_this_level) pairs

    function push(val):
        if stack is empty:
            stack.push((val, val))
        else:
            currentMin = min(val, stack.top().min)
            stack.push((val, currentMin))

    function pop():
        stack.pop()

    function top():
        return stack.top().value

    function getMin():
        return stack.top().min

Solution Code

Python

min_stack_pair.py

class MinStack:
    """Min Stack using single stack with (value, min) pairs.

    Each element in the stack is a tuple of (value, min_at_this_level).
    The min_at_this_level is the minimum value from the bottom up to
    and including the current element.

    Time: O(1) per operation
    Space: O(n)
    """

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

    def push(self, val: int) -> None:
        if not self.stack:
            # First element: value is the minimum
            self.stack.append((val, val))
        else:
            # Store both value and the minimum up to this point
            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]


# Example usage
stack = MinStack()
stack.push(-2)
stack.push(0)
stack.push(-3)
print(f"Min: {stack.getMin()}")  # -3
stack.pop()
print(f"Top: {stack.top()}")     # 0
print(f"Min: {stack.getMin()}")  # -2

C++

min_stack_pair.cpp

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

class MinStack {
private:
    stack<pair<int, int>> stack;

public:
    /**
     * Min Stack using single stack with (value, min) pairs.
     *
     * Each element in the stack is a pair of (value, min_at_this_level).
     * The min_at_this_level is the minimum value from the bottom up to
     * and including the current element.
     *
     * Time: O(1) per operation
     * Space: O(n)
     */

    void push(int val) {
        if (stack.empty()) {
            // First element: value is the minimum
            stack.push({val, val});
        } else {
            // Store both value and the minimum up to this point
            int current_min = min(val, stack.top().second);
            stack.push({val, current_min});
        }
    }

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

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

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

int main() {
    MinStack stack;
    stack.push(-2);
    stack.push(0);
    stack.push(-3);
    cout << "Min: " << stack.getMin() << endl;  // -3
    stack.pop();
    cout << "Top: " << stack.top() << endl;     // 0
    cout << "Min: " << stack.getMin() << endl;  // -2
    return 0;
}

Java

min_stack_pair.java

import java.util.Stack;

public class MinStackPair {
    /**
     * Min Stack using single stack with (value, min) pairs.
     *
     * Each element in the stack is a pair of (value, min_at_this_level).
     * The min_at_this_level is the minimum value from the bottom up to
     * and including the current element.
     *
     * Time: O(1) per operation
     * Space: O(n)
     */

    private Stack<int[]> stack;

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

    public void push(int val) {
        if (stack.isEmpty()) {
            // First element: value is the minimum
            stack.push(new int[]{val, val});
        } else {
            // Store both value and the minimum up to this point
            int currentMin = Math.min(val, stack.peek()[1]);
            stack.push(new int[]{val, currentMin});
        }
    }

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

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

    public int getMin() {
        return stack.peek()[1];
    }

    public static void main(String[] args) {
        MinStackPair stack = new MinStackPair();
        stack.push(-2);
        stack.push(0);
        stack.push(-3);
        System.out.println("Min: " + stack.getMin());  // -3
        stack.pop();
        System.out.println("Top: " + stack.top());     // 0
        System.out.println("Min: " + stack.getMin());  // -2
    }
}

JavaScript

min_stack_pair.js

/**
 * Min Stack using single stack with (value, min) pairs.
 *
 * Each element in the stack is an object of {value, min}.
 * The min is the minimum value from the bottom up to
 * and including the current element.
 *
 * Time: O(1) per operation
 * Space: O(n)
 */
class MinStack {
  constructor() {
    this.stack = [];
  }

  push(val) {
    if (this.stack.length === 0) {
      // First element: value is the minimum
      this.stack.push({ value: val, min: val });
    } else {
      // Store both value and the minimum up to this point
      const currentMin = Math.min(val, this.stack[this.stack.length - 1].min);
      this.stack.push({ value: val, min: currentMin });
    }
  }

  pop() {
    this.stack.pop();
  }

  top() {
    return this.stack[this.stack.length - 1].value;
  }

  getMin() {
    return this.stack[this.stack.length - 1].min;
  }
}

// Example usage
const stack = new MinStack();
stack.push(-2);
stack.push(0);
stack.push(-3);
console.log(`Min: ${stack.getMin()}`);  // -3
stack.pop();
console.log(`Top: ${stack.top()}`);     // 0
console.log(`Min: ${stack.getMin()}`);  // -2

Rust

min_stack_pair.rs

/**
 * Min Stack using single stack with (value, min) pairs.
 *
 * Each element in the stack is a tuple of (value, min_at_this_level).
 * The min_at_this_level is the minimum value from the bottom up to
 * and including the current element.
 *
 * Time: O(1) per operation
 * Space: O(n)
 */
struct MinStack {
    stack: Vec<(i32, i32)>,
}

impl MinStack {
    fn new() -> Self {
        MinStack {
            stack: Vec::new(),
        }
    }

    fn push(&mut self, val: i32) {
        if self.stack.is_empty() {
            // First element: value is the minimum
            self.stack.push((val, val));
        } else {
            // Store both value and the minimum up to this point
            let current_min = val.min(self.stack.last().unwrap().1);
            self.stack.push((val, current_min));
        }
    }

    fn pop(&mut self) {
        self.stack.pop();
    }

    fn top(&self) -> i32 {
        self.stack.last().unwrap().0
    }

    fn get_min(&self) -> i32 {
        self.stack.last().unwrap().1
    }
}

fn main() {
    let mut stack = MinStack::new();
    stack.push(-2);
    stack.push(0);
    stack.push(-3);
    println!("Min: {}", stack.get_min());  // -3
    stack.pop();
    println!("Top: {}", stack.top());      // 0
    println!("Min: {}", stack.get_min());  // -2
}

Go

min_stack_pair.go

package main

import (
  "fmt"
)

/**
 * Min Stack using single stack with (value, min) pairs.
 *
 * Each element in the stack is a struct of (value, min_at_this_level).
 * The min_at_this_level is the minimum value from the bottom up to
 * and including the current element.
 *
 * Time: O(1) per operation
 * Space: O(n)
 */
type Element struct {
  value int
  min   int
}

type MinStack struct {
  stack []Element
}

func NewMinStack() *MinStack {
  return &MinStack{
    stack: []Element{},
  }
}

func (ms *MinStack) Push(val int) {
  if len(ms.stack) == 0 {
    // First element: value is the minimum
    ms.stack = append(ms.stack, Element{value: val, min: val})
  } else {
    // Store both value and the minimum up to this point
    currentMin := val
    if ms.stack[len(ms.stack)-1].min < val {
      currentMin = ms.stack[len(ms.stack)-1].min
    }
    ms.stack = append(ms.stack, Element{value: val, min: currentMin})
  }
}

func (ms *MinStack) Pop() {
  ms.stack = ms.stack[:len(ms.stack)-1]
}

func (ms *MinStack) Top() int {
  return ms.stack[len(ms.stack)-1].value
}

func (ms *MinStack) GetMin() int {
  return ms.stack[len(ms.stack)-1].min
}

func main() {
  stack := NewMinStack()
  stack.Push(-2)
  stack.Push(0)
  stack.Push(-3)
  fmt.Printf("Min: %d\n", stack.GetMin()) // -3
  stack.Pop()
  fmt.Printf("Top: %d\n", stack.Top())    // 0
  fmt.Printf("Min: %d\n", stack.GetMin()) // -2
}

Common mistakes

Watch for these pitfalls

• Forgetting to sync the min stack on pop() — if you only pop from the main stack and not the min stack, the two get out of sync.
• Computing min inside pop() instead of push() — the minimum must be stored as you push, not computed later.
• Using a heap or priority queue — those are O(log n) per operation, not O(1).
• Recomputing the minimum by scanning the stack on getMin() — this is O(n), defeating the entire purpose.
• Not handling duplicate minimums — if the same minimum value appears multiple times, make sure each occurrence is tracked in the min stack.
• Off-by-one errors when storing pairs — ensure the min value in a pair reflects the minimum up to that point, not just the current value.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

min_stack_space_optimized.py

"""
Solution for Min Stack
"""

def solve():
    """Implementation for approach 3 of Min Stack"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

min_stack_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Min Stack
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

MinStackSpaceOptimized.java

/**
 * Solution for Min Stack
 * Approach 3
 */
public class MinStackSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

min_stack_space_optimized.js

/**
 * Solution for Min Stack
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

min_stack_space_optimized.rs

/// Solution for Min Stack
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

min_stack_space_optimized.go

package main

import "fmt"

// Solution for Min Stack
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Simplify Path ↗ Medium #71
• LRU Cache ↗ Medium #146
• Implement Stack using Queues ↗ Easy #225
• Implement Queue using Stacks ↗ Easy #232

Interview Tips

Key trade-offs to discuss

• Dual Stack vs. Pairs: Both are O(1) time. Dual Stack is clearer and easier to explain. Pairs are more compact but require careful bookkeeping.
• Why not use a heap? Heaps give O(log n) per operation, and you’d need to remove specific elements (no efficient removal for min-heaps).
• Why not recompute on getMin()? The problem explicitly demands O(1) time for getMin(). Scanning the stack is O(n).
• Edge cases to mention: Single element (min = that element), duplicate minimums (each occurrence needs a min stack entry), negative numbers (all approaches handle them), and large stacks (space is O(n) either way).
• Follow-up — Median Finder: A harder version where you track both min and median; this requires a heap-based approach.

← Previous
#154 Find Minimum in Rotated Sorted Array II Next
#156 Binary Tree Upside Down →