Min Stack: Auxiliary stack Pattern

Learning Outcome

After this lesson, you should be able to design a stack that supports push, pop, top, and getMin in constant time.

Problem Statement

Design a stack that supports standard stack operations and can return the minimum element currently in the stack in O(1) time.

Brute Force Approach

Use a normal stack and scan all current values whenever getMin is called.

That makes getMin O(n), which breaks the requirement.

Optimized Approach

Store each pushed value together with the minimum value at that moment. Then the stack top always knows the current minimum.

Another valid version uses two stacks: one for values and one for minimums. The pair approach is compact and easy to dry-run.

Exact Pseudocode

stack = empty stack of (value, currentMin)
push(value):
  if stack is empty:
    currentMin = value
  else:
    currentMin = min(value, stack.top.currentMin)
  push (value, currentMin)
pop():
  pop stack
top():
  return stack.top.value
getMin():
  return stack.top.currentMin
  

Reference Code

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

    def push(self, val):
        current_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, current_min))

    def pop(self):
        self.stack.pop()

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

    def getMin(self):
        return self.stack[-1][1]
  

Sample Dry Run

Complexity

Edge Cases

• Duplicate minimum values.
• Negative values.
• Calling operations only when the stack is valid according to platform constraints.

Interview Checklist

• Do not scan the full stack in getMin.
• Store the minimum at each push.
• Handle duplicate minimums correctly.

FAQs