IntermediateStacks, Queues, Heaps

Monotonic Deque

Use a deque to maintain window candidates in increasing/decreasing order for O(1) queries per slide

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

Core Idea

Pop from back to maintain monotonicity and pop from front when index leaves the window; front holds the answer.

When to Use

Use for sliding window max/min, shortest subarray with sum ≥ K using prefix sums, and other windowed monotonic predicates.

General Recognition Cues
General indicators that this pattern might be applicable
  • Sliding window max/min
  • Windowed prefix sums
  • Need O(1) per slide
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Window Max/Min

Maintain decreasing (max) or increasing (min) deque of indices

When to Use This Variant
  • Sliding window maximum/minimum
  • Indices not values
  • O(n) total
Use Case
Array window extrema
Advantages
  • Linear time
  • Small memory
  • Deterministic
Implementation
from collections import deque
def max_sliding_window(nums, k):
    dq = deque()  # indices, decreasing by value
    res = []
    for i, v in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= v:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res
2

Shortest Subarray

Use increasing deque over prefix sums to find shortest valid range

When to Use This Variant
  • Prefix sums
  • Sum ≥ K
  • Pop from front/back
Use Case
Shortest subarray with constraint
Advantages
  • Linear time
  • Works with negatives
  • Elegant
Implementation
from collections import deque
def shortest_subarray_at_least_k(nums, k):
    # Works with negatives using prefix sums + increasing deque
    n = len(nums)
    pref = [0]
    for x in nums:
        pref.append(pref[-1] + x)
    ans = n + 1
    dq = deque()
    for i, s in enumerate(pref):
        while dq and s <= pref[dq[-1]]:
            dq.pop()
        while dq and s - pref[dq[0]] >= k:
            ans = min(ans, i - dq.popleft())
        dq.append(i)
    return ans if ans <= n else -1
3

Convex Hull Trick

Maintain lower/upper hull of lines to query minima/maxima

When to Use This Variant
  • DP optimization
  • Lines of form ax+b
  • Queries increasing x
Use Case
DP speedups with linear costs
Advantages
  • Amortized O(1) query with monotone x
  • Lower complexity than naive
  • Powerful for DP
Implementation
# Monotone CHT for increasing slopes and increasing x queries
class CHT:
    def __init__(self):
        self.lines = []  # (m, b)
    def bad(self, l1, l2, l3):
        # Remove middle if intersection(l1,l2) >= intersection(l2,l3)
        return (l3[1]-l1[1]) * (l1[0]-l2[0]) <= (l2[1]-l1[1]) * (l1[0]-l3[0])
    def add(self, m, b):
        self.lines.append((m, b))
        while len(self.lines) >= 3 and self.bad(self.lines[-3], self.lines[-2], self.lines[-1]):
            self.lines.pop(-2)
    def query(self, x):
        # Assuming non-decreasing x
        while len(self.lines) >= 2 and self.f(self.lines[0], x) >= self.f(self.lines[1], x):
            self.lines.pop(0)
        return self.f(self.lines[0], x)
    def f(self, line, x):
        return line[0]*x + line[1]
Common Pitfalls
Watch out for these common mistakes
  • Forgetting to drop out-of-window indices
  • Wrong monotone direction
  • Comparing values not indices
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 index enters and leaves deque once.

Space Complexity
O(k)

Deque stores up to window size indices.

Ready to test your knowledge?

Test your pattern recognition with interactive questions