BeginnerStacks, Queues, Heaps

Min/Max Stack

Augment stack to support O(1) getMin/getMax or use a deque for window min/max

Time: O(1) ops
Space: O(n)
Pattern Overview

Core Idea

Track running min/max alongside values or use monotonic deque for window extrema.

When to Use

Use for min stack design, and sliding window extrema in arrays.

General Recognition Cues
General indicators that this pattern might be applicable
  • O(1) min/max
  • Window extrema
  • Augmented push/pop
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

O(1) Min Stack

Maintain paired min with each push

When to Use This Variant
  • getMin() O(1)
Use Case
Design min stack
Advantages
  • Fast queries
  • Simple
Implementation
class MinStack:
    def __init__(self): self.st=[]
    def push(self, x): self.st.append((x, x if not self.st else min(x, self.st[-1][1])))
    def pop(self): self.st.pop()
    def top(self): return self.st[-1][0]
    def getMin(self): return self.st[-1][1]
2

Monotonic Queue

Deque for window min/max

When to Use This Variant
  • Window size k
Use Case
Sliding extrema
Advantages
  • Linear time
  • Compact
Implementation
from collections import deque
class MonotonicQueue:
    def __init__(self): self.dq = deque()
    def push(self, x):
        while self.dq and self.dq[-1] < x: self.dq.pop()
        self.dq.append(x)
    def pop(self, x):
        if self.dq and self.dq[0] == x: self.dq.popleft()
    def max(self): return self.dq[0] if self.dq else None
Common Pitfalls
Watch out for these common mistakes
  • Syncing aux stack with main
  • Handling duplicates correctly
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(1) ops

Each operation is O(1).

Space Complexity
O(n)

Stack/deque holds elements.

Ready to test your knowledge?

Test your pattern recognition with interactive questions