IntermediateStacks, Queues, Heaps

Monotonic Stack

Maintain increasing/decreasing stacks to find next/previous greater or smaller elements efficiently

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

Core Idea

Push indices/heights while maintaining monotonicity; pop when invariant breaks to resolve answers spanning the popped element.

When to Use

Use for next greater/smaller queries, histogram rectangles, stock span, or removing digits for minimal number.

General Recognition Cues
General indicators that this pattern might be applicable
  • Next/previous greater or smaller
  • Span length until boundary
  • Histogram rectangle area
  • Local monotonic neighborhoods
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Next Greater/Smaller

Pop while current breaks monotonic property to discover next boundary

When to Use This Variant
  • Next greater element
  • Daily temperatures
  • Remove K digits
Use Case
Next boundary queries to the right/left
Advantages
  • Linear time
  • Simple invariant
  • Works with indices/values
Implementation
def next_greater(nums):
    res, stack = [-1] * len(nums), []  # stack of indices
    for i, v in enumerate(nums):
        while stack and nums[stack[-1]] < v:
            res[stack.pop()] = v
        stack.append(i)
    return res
2

Largest Rectangle

Use increasing stack of heights; compute area when a lower bar appears

When to Use This Variant
  • Histogram area
  • Popping computes width
  • Sentinel trick
Use Case
Largest rectangle in histogram/1D skyline
Advantages
  • O(n) with stack
  • Handles plateaus
  • Deterministic
Implementation
def largest_rectangle(heights):
    st = []  # (index)
    max_area = 0
    for i, h in enumerate(heights + [0]):
        while st and heights[st[-1]] > h:
            height = heights[st.pop()]
            left = st[-1] + 1 if st else 0
            width = i - left
            max_area = max(max_area, height * width)
        st.append(i)
    return max_area
3

Stock Span

Monotonic stack of decreasing prices to compute span

When to Use This Variant
  • Consecutive days until greater
  • Span length
  • Streaming updates
Use Case
Online span queries
Advantages
  • Amortized O(1) per update
  • Compact state
  • Easy to implement
Implementation
class StockSpanner:
    def __init__(self):
        self.st = []  # (price, span)
    def next(self, price: int) -> int:
        span = 1
        while self.st and self.st[-1][0] <= price:
            span += self.st.pop()[1]
        self.st.append((price, span))
        return span
Common Pitfalls
Watch out for these common mistakes
  • Forgetting sentinels at ends
  • Not storing indices when needed
  • Infinite loops from improper pops
  • Off-by-one on width calculation
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(n)

Each element is pushed and popped at most once.

Space Complexity
O(n)

Stack may hold indices in worst case.

Ready to test your knowledge?

Test your pattern recognition with interactive questions