LeetCode 155 - Min Stack

The problem asks us to design a custom stack data structure that behaves like a normal stack, while also supporting an additional operation called getMin(). This operation must return the minimum value currently stored in the stack, and it must do so in constant time, O(1).

leetcodemediumstackdesign

LeetCode Problem 155

Difficulty: 🟡 Medium
Topics: Stack, Design

Solution

Problem Understanding

The problem asks us to design a custom stack data structure that behaves like a normal stack, while also supporting an additional operation called getMin(). This operation must return the minimum value currently stored in the stack, and it must do so in constant time, O(1).

A normal stack already supports these standard operations efficiently:

  • push(val) inserts an element onto the top
  • pop() removes the top element
  • top() returns the top element

The challenge is adding getMin() while preserving constant time complexity for every operation.

The input in LeetCode is represented as a sequence of method calls. For example:

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

This means:

  1. Create a new MinStack
  2. Push -2
  3. Push 0
  4. Push -3
  5. Retrieve the minimum
  6. Pop the top
  7. Retrieve the top
  8. Retrieve the minimum again

The expected output is:

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

The constraints are important:

  • Up to 3 * 10^4 operations
  • Values can range from -2^31 to 2^31 - 1
  • pop, top, and getMin are always called on non-empty stacks

These constraints tell us that efficiency matters. A solution that scans the entire stack every time getMin() is called would become too slow in the worst case.

Several edge cases are important:

  • Multiple identical minimum values
  • Popping the current minimum
  • Negative numbers
  • A stack with only one element
  • Alternating pushes and pops that frequently change the minimum

The problem guarantees that invalid operations will never occur, so we do not need to handle popping from an empty stack.

Approaches

Brute Force Approach

The simplest implementation uses a single stack.

  • push() appends the value
  • pop() removes the last value
  • top() returns the last value
  • getMin() scans the entire stack and returns the smallest element

This approach is correct because scanning every element always finds the true minimum. However, the problem specifically requires constant time operations. Scanning the stack takes O(n) time, which violates the requirement.

If there are many getMin() calls on a large stack, the performance becomes inefficient.

Optimal Approach

The key insight is that we should not recompute the minimum repeatedly. Instead, we should store enough information during each push() operation so that the minimum is always immediately available.

A common technique is to maintain a second stack called min_stack.

  • The main stack stores all values
  • The min stack stores the minimum value seen so far at each depth

For every push:

  • Push the value onto the main stack
  • Push the new minimum onto the min stack

For every pop:

  • Pop from both stacks

This ensures:

  • The top of the main stack is always the current top element
  • The top of the min stack is always the current minimum

Every operation becomes O(1).

Approach Time Complexity Space Complexity Notes
Brute Force push/pop/top: O(1), getMin: O(n) O(n) Uses one stack and scans for minimum
Optimal O(1) for all operations O(n) Uses an additional stack to track minimums

Algorithm Walkthrough

  1. Initialize two stacks.

The first stack stores all pushed values normally. The second stack stores the minimum value corresponding to each stack depth. 2. During push(val):

Push val onto the main stack.

Then determine the new minimum:

  • If the min stack is empty, val becomes the minimum
  • Otherwise, compare val with the current minimum
  • Push the smaller value onto the min stack

This guarantees that the top of the min stack always represents the minimum value of the stack at that moment. 3. During pop():

Remove the top element from both stacks.

Since both stacks always have the same size, removing from both keeps them synchronized. 4. During top():

Return the last element from the main stack. 5. During getMin():

Return the last element from the min stack.

Since the min stack stores the minimum at every depth, this operation is constant time.

Why it works

The core invariant is:

At every stack depth i, min_stack[i] stores the minimum value among all elements in stack[0:i+1].

Because this invariant is maintained during every push and pop, the top of the min stack always represents the current minimum element of the entire stack.

Python Solution

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:
            self.min_stack.append(val)
        else:
            current_min = self.min_stack[-1]
            self.min_stack.append(min(val, current_min))

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

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

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

# 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()

The implementation uses two Python lists as stacks.

self.stack stores the actual elements pushed by the user.

self.min_stack stores the minimum value corresponding to every stack position. This means both stacks always have the same length.

Inside push(), we first append the value to the main stack. Then we compare the new value with the current minimum. The smaller value is appended to min_stack.

Inside pop(), both stacks remove their top elements together so they remain synchronized.

top() simply returns the last element of the main stack.

getMin() returns the last element of the min stack, which is always the minimum value currently present in the stack.

Go Solution

type MinStack struct {
	stack    []int
	minStack []int
}

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

func (this *MinStack) Push(val int) {
	this.stack = append(this.stack, val)

	if len(this.minStack) == 0 {
		this.minStack = append(this.minStack, val)
	} else {
		currentMin := this.minStack[len(this.minStack)-1]

		if val < currentMin {
			this.minStack = append(this.minStack, val)
		} else {
			this.minStack = append(this.minStack, currentMin)
		}
	}
}

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

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

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

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

The Go solution follows the same logic as the Python version but uses slices instead of Python lists.

Popping from a stack in Go is done by slicing:

stack = stack[:len(stack)-1]

Unlike Python, Go does not provide built-in stack operations, so slices are commonly used to simulate stacks efficiently.

The constraints guarantee valid operations, so no additional empty-stack checks are required.

Worked Examples

Example 1

Input:

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

Step-by-step Trace

Operation Main Stack Min Stack Returned Value
Initialize [] [] null
push(-2) [-2] [-2] null
push(0) [-2, 0] [-2, -2] null
push(-3) [-2, 0, -3] [-2, -2, -3] null
getMin() [-2, 0, -3] [-2, -2, -3] -3
pop() [-2, 0] [-2, -2] null
top() [-2, 0] [-2, -2] 0
getMin() [-2, 0] [-2, -2] -2

Notice how the min stack stores the minimum value at every level:

  • After pushing 0, the minimum remains -2
  • After pushing -3, the minimum becomes -3
  • After popping -3, the previous minimum -2 is automatically restored

Complexity Analysis

Measure Complexity Explanation
Time O(1) Every operation uses only direct stack access
Space O(n) Two stacks store up to n elements

Each operation performs only constant-time stack operations such as append, pop, and indexing.

The additional min stack requires extra memory proportional to the number of elements in the main stack. Therefore, the total space complexity is linear.

Test Cases

# Basic example from problem statement
stack = MinStack()
stack.push(-2)
stack.push(0)
stack.push(-3)
assert stack.getMin() == -3  # minimum after multiple pushes
stack.pop()
assert stack.top() == 0      # top after pop
assert stack.getMin() == -2  # minimum restored after pop

# Single element stack
stack = MinStack()
stack.push(5)
assert stack.top() == 5      # only element is top
assert stack.getMin() == 5   # only element is minimum

# Increasing values
stack = MinStack()
stack.push(1)
stack.push(2)
stack.push(3)
assert stack.getMin() == 1   # first element remains minimum

# Decreasing values
stack = MinStack()
stack.push(3)
stack.push(2)
stack.push(1)
assert stack.getMin() == 1   # newest element becomes minimum

# Duplicate minimum values
stack = MinStack()
stack.push(2)
stack.push(1)
stack.push(1)
stack.push(3)
assert stack.getMin() == 1   # duplicate minimum exists
stack.pop()
assert stack.getMin() == 1   # minimum still exists
stack.pop()
assert stack.getMin() == 1   # second duplicate still exists
stack.pop()
assert stack.getMin() == 2   # minimum restored

# Negative numbers
stack = MinStack()
stack.push(-1)
stack.push(-5)
stack.push(-3)
assert stack.getMin() == -5  # negative minimum

# Alternating push and pop
stack = MinStack()
stack.push(10)
stack.push(5)
assert stack.getMin() == 5   # minimum updated
stack.pop()
assert stack.getMin() == 10  # minimum restored
stack.push(2)
assert stack.getMin() == 2   # new minimum

# Large integer boundaries
stack = MinStack()
stack.push(-2**31)
stack.push(2**31 - 1)
assert stack.getMin() == -2**31  # minimum handles extreme values
Test Why
Problem example Verifies standard behavior
Single element Tests smallest valid stack
Increasing values Ensures minimum remains unchanged
Decreasing values Ensures minimum updates correctly
Duplicate minimums Verifies proper handling of repeated minimums
Negative numbers Confirms support for negative values
Alternating operations Tests synchronization between stacks
Integer boundaries Confirms extreme values are handled correctly

Edge Cases

Duplicate Minimum Values

One subtle issue occurs when the minimum value appears multiple times.

For example:

push(2)
push(1)
push(1)

If we only tracked unique minimums, popping one 1 could incorrectly remove the minimum even though another 1 still exists.

The implementation avoids this problem by storing the minimum value at every stack depth. Each push records the current minimum again, even if it is unchanged.

Popping the Current Minimum

Another common source of bugs occurs when the top element is also the current minimum.

For example:

push(3)
push(2)
push(1)
pop()

After removing 1, the minimum should revert to 2.

Because the min stack stores historical minimum values at every depth, removing the top automatically restores the previous minimum correctly.

Negative Numbers and Integer Limits

The constraints allow values as small as -2^31 and as large as 2^31 - 1.

Some implementations accidentally assume only positive numbers or use incorrect comparisons.

This solution works correctly for all valid integer values because it only relies on standard integer comparisons and does not perform arithmetic operations that could overflow.