Monotone Stacks and Monotone Queues

Chapter 6: Monotone Stacks and Monotone Queues

You're standing among a row of skyscrapers, trying to find the first taller building to the right of each one. The naive approach scans rightward for every building—O(n²). But if you walk from right to left while maintaining a stack where buildings get taller toward the bottom, each building only needs to pop a few shorter ones to find its answer. Every element enters the stack at most once and leaves at most once: O(n) total.

This is the core idea behind the monotone stack (also called a monotonic stack): by maintaining the monotonicity of elements within the stack, we reduce "find the first element in some direction satisfying some condition" problems from O(n²) to O(n).

Its sibling, the monotone queue (monotonic deque), applies the same principle to sliding windows: maintain a double-ended queue with monotonic elements, yielding O(1) access to the window's maximum or minimum.

These two data structures appear to be "variants of stacks and queues," but they are really a thinking pattern: exploit monotonicity to eliminate candidates that can never be answers, trading space for the time that brute-force enumeration would consume. Master them, and you unlock an entire family of seemingly complex problems.

Level 1 · What You Need to Know

1.1 The Concept of a Monotone Stack

A monotone stack is an ordinary stack, but we maintain an invariant during its use: elements from bottom to top are monotonically increasing or monotonically decreasing.

To maintain this invariant, before pushing a new element, we repeatedly pop stack elements that violate the monotonicity until the top satisfies the condition (or the stack is empty), then push the new element.

Monotone increasing stack (values increase from bottom to top):

def monotone_increasing_stack(nums):
    """
    Maintains a monotone increasing stack (bottom to top, values increase).
    Each pop means: the popped element has found the next smaller element to its right.
    """
    stack = []  # stores indices
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] >= num:
            # nums[i] is the first smaller element to the right of nums[stack[-1]]
            popped = stack.pop()
            # process the popped element
        stack.append(i)

Monotone decreasing stack (values decrease from bottom to top):

def monotone_decreasing_stack(nums):
    """
    Maintains a monotone decreasing stack (bottom to top, values decrease).
    Each pop means: the popped element has found the next greater element to its right.
    """
    stack = []  # stores indices
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] <= num:
            # nums[i] is the first greater element to the right of nums[stack[-1]]
            popped = stack.pop()
            # process the popped element
        stack.append(i)

Key insight: The stack typically stores indices, not values. With indices you can look up values, but not vice versa (values may repeat). Moreover, many problems require "distance" (i.e., index difference).

1.2 Next Greater Element (LeetCode #496, #503)

Problem: Given an array, for each element, find the first element to its right that is greater. If none exists, record -1.

This is the most classic introductory monotone stack problem.

def next_greater_element(nums: list[int]) -> list[int]:
    """
    For each element in nums, find the next greater value to its right.
    
    Approach: Maintain a monotone decreasing stack. When the new element
    is greater than the stack top, the stack top's "next greater element"
    is the current element.
    
    Time complexity: O(n) — each element pushed and popped at most once
    Space complexity: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices; corresponding values decrease bottom-to-top
    
    for i in range(n):
        # Current element > stack top → stack top found its answer
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    
    # Elements remaining in stack have no next greater value; keep -1
    return result


# Test
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums))  # [4, 2, 4, -1, -1]

Detailed execution trace (for [2, 1, 2, 4, 3]):

Final result = [4, 2, 4, -1, -1].

LeetCode #496 — Next Greater Element I:

def next_greater_element_i(nums1: list[int], nums2: list[int]) -> list[int]:
    """
    nums1 is a subset of nums2. For each element in nums1,
    find it in nums2, then find the next greater element to its right.
    
    Approach: Use monotone stack on nums2 to build a hash map: value → next greater.
    Then look up each element of nums1.
    """
    next_greater = {}
    stack = []
    
    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)
    
    for num in stack:
        next_greater[num] = -1
    
    return [next_greater[num] for num in nums1]

1.3 Daily Temperatures (LeetCode #739)

Problem: Given a list of daily temperatures, return a list where each entry says how many days you must wait for a warmer temperature. If no warmer day exists afterward, return 0.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    """
    Classic monotone stack: find the "distance" to the next greater element.
    
    Maintain a monotone decreasing stack (temperatures decrease bottom-to-top).
    When a new temperature exceeds the stack top, that day's answer =
    current day - stack top day.
    
    Time: O(n)
    Space: O(n)
    """
    n = len(temperatures)
    answer = [0] * n
    stack = []  # stores indices
    
    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            prev_day = stack.pop()
            answer[prev_day] = i - prev_day
        stack.append(i)
    
    return answer


# Test
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))  # [1, 1, 4, 2, 1, 1, 0, 0]

Why store indices instead of values: This problem requires computing "how many days to wait," which is the difference between indices. If the stack stored temperature values, you couldn't compute the day gap.

1.4 Trapping Rain Water (LeetCode #42) — Monotone Stack Solution

Problem: Given n non-negative integers representing bar heights (width 1 each), compute how much water can be trapped after rain.

Monotone stack approach: We maintain a monotone decreasing stack. When we encounter a bar taller than the stack top, the stack top is "sandwiched" between two taller bars, forming a trough that can hold water.

def trap(height: list[int]) -> int:
    """
    Trapping Rain Water - monotone stack solution
    
    Maintain a decreasing stack. When height[i] > height[stack[-1]],
    the stack top forms the bottom of a trough. After popping, the new
    stack top is the left boundary, i is the right boundary.
    Water = (min(left_height, right_height) - bottom_height) * width
    
    Time: O(n)
    Space: O(n)
    """
    stack = []  # indices with monotonically decreasing heights
    water = 0
    
    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()  # trough bottom
            if not stack:
                break  # no left boundary
            left = stack[-1]  # left boundary
            width = i - left - 1
            h = min(height[left], height[i]) - height[bottom]
            water += width * h
        stack.append(i)
    
    return water


# Test
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap(height))  # 6

Visualization (for [0,1,0,2,1,0,1,3,2,1,2,1]):

        #
    #   ##
 #  ## ####
#_##_#_####_   (underscores represent water)

1.5 Largest Rectangle in Histogram (LeetCode #84)

Problem: Given n non-negative integers representing histogram bar heights (width 1), find the area of the largest rectangle that can be formed.

Core idea: For each bar, using its height as the rectangle height, how far can it extend left and right? It extends until the first shorter bar. So the problem reduces to: for each element, find the first smaller to the left and first smaller to the right.

def largest_rectangle_area(heights: list[int]) -> int:
    """
    Largest Rectangle in Histogram - monotone stack with sentinels
    
    Maintain a monotone increasing stack (heights increase bottom-to-top).
    When a new bar is shorter than the stack top, the stack top has found
    its right boundary (current bar) and left boundary (new stack top).
    
    Trick: Add 0 to both ends of heights to avoid boundary checks.
    - Left sentinel ensures the stack is never empty
    - Right sentinel ensures all bars get processed
    
    Time: O(n)
    Space: O(n)
    """
    heights = [0] + heights + [0]  # sentinels
    stack = [0]  # start with left sentinel
    max_area = 0
    
    for i in range(1, len(heights)):
        while heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, h * width)
        stack.append(i)
    
    return max_area


# Test
heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_area(heights))  # 10  (bars 5,6 form 5*2=10)

The elegance of sentinels:

1. Left sentinel (heights[0] = 0): The stack is never empty, so stack[-1] always gives a valid left boundary.
2. Right sentinel (heights[-1] = 0): Height 0 is shorter than all bars, so every bar in the stack gets processed by the end.

Without sentinels, you'd need extra code after the loop to handle remaining stack elements.

1.6 Monotone Queue: Sliding Window Maximum (LeetCode #239)

Problem: Given an array and window size k, return the maximum of each window.

Brute force: For each window, scan k elements for the max: O(nk).

Monotone queue solution: Maintain a double-ended queue (deque) storing indices, where corresponding values are monotonically decreasing from front to back. The front always holds the current window's maximum.

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """
    Sliding Window Maximum - monotone queue solution
    
    Maintain a decreasing monotone deque:
    1. Before enqueueing, pop from back all elements smaller than the new one
    2. Append new index to back
    3. If front index has slid out of window, pop from front
    4. Once window is formed (i >= k-1), front is the window max
    
    Time: O(n) — each element enqueued and dequeued at most once
    Space: O(k)
    """
    dq = deque()  # indices with decreasing values
    result = []
    
    for i in range(len(nums)):
        # 1. Remove from back all elements smaller than current
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        
        # 2. Enqueue current
        dq.append(i)
        
        # 3. Remove front if out of window
        if dq[0] <= i - k:
            dq.popleft()
        
        # 4. Record maximum once window is fully formed
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result


# Test
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))  # [3, 3, 5, 5, 6, 7]

Why are popped elements "useless"?

Suppose index j is in the deque and index i arrives (i > j) with nums[i] >= nums[j]. Then:

• In any future window containing j, i is also present (since i > j, i leaves later)
• Since nums[i] >= nums[j], j can never be the maximum in such windows
• So j can be safely discarded

This is the core logic of monotone queues: eliminate candidates that can never be the answer.

Execution trace (nums = [1, 3, -1, -3, 5, 3, 6, 7], k=3):

1.7 Common Mistakes

Level 2 · How It Works Under the Hood

2.1 Time Complexity: Why O(n) and Not O(n²)

A common beginner concern: the outer loop is O(n), and the inner while loop pops elements—doesn't nesting make it O(n²) in the worst case?

The answer is no. We need amortized analysis to understand why.

Core argument: Each element is pushed at most once and popped at most once.

• The outer for-loop executes n iterations, each performing one stack.append(i): n total pushes.
• The inner while loop performs stack.pop(), but you can only pop what was previously pushed. With at most n pushes, there are at most n pops total.

Total operations = n pushes + at most n pops = O(2n) = O(n).

Analogy: Imagine a revolving door with n people in line. Each person enters exactly once and exits exactly once. No matter how complex the "popping" process looks inside, total operations never exceed 2n.

Formal proof (Aggregate Analysis):

Let T(n) be the total number of operations. Define potential function Φ = number of elements in the stack.

For the i-th iteration:

• Let kᵢ = number of elements popped by the while loop
• Actual cost: cᵢ = kᵢ + 1 (kᵢ pops + 1 push)
• Potential change: ΔΦᵢ = 1 - kᵢ (pushed 1, popped kᵢ)
• Amortized cost: ĉᵢ = cᵢ + ΔΦᵢ = (kᵢ + 1) + (1 - kᵢ) = 2

The amortized cost per iteration is constant (2), so total amortized cost = 2n = O(n).

2.2 Monotone Stack vs. Brute Force

Using "next greater element" as an example:

Brute force:

def next_greater_brute(nums):
    """O(n²) brute force: for each element, scan rightward"""
    n = len(nums)
    result = [-1] * n
    for i in range(n):
        for j in range(i + 1, n):
            if nums[j] > nums[i]:
                result[i] = nums[j]
                break
    return result

Performance comparison:

Why brute force is slow: For a decreasing sequence [n, n-1, ..., 2, 1], every element scans to the end without finding a greater value. Total comparisons = n + (n-1) + ... + 1 = n(n-1)/2.

Why the monotone stack is fast: It exploits transitivity. If a < b < c, then a's next greater element cannot be c (because b appears first and b > a). Brute force ignores this information; the monotone stack implicitly encodes this relationship through its monotonicity invariant.

2.3 Monotone Queue Implementation Details with Deque

Python's collections.deque is implemented as a doubly-linked list of blocks, providing O(1) operations at both ends.

Comparison between regular queue and monotone queue:

Why not use heapq (priority queue) for sliding window maximum?

A heap can retrieve the maximum in O(log n), but has a fatal problem: removing a non-top element costs O(n). When the window slides, if the departing element isn't at the heap's top, it's expensive to remove.

You can use "lazy deletion" (mark as deleted, skip when accessing top), but worst case the heap grows to O(n) elements, each operation O(log n), total O(n log n). The monotone queue is strictly O(n)—better.

2.4 Circular Arrays and the Modulo Trick

LeetCode #503 — Next Greater Element II: The array is circular; the element after the last is the first.

def next_greater_elements_circular(nums: list[int]) -> list[int]:
    """
    Next greater element in a circular array.
    
    Trick: "Unroll" the array to twice its length, use modulo for original indices.
    Iterate through 2n positions but only record answers for the first n.
    
    Why is two passes enough? Each element needs at most one full loop to find
    its answer. If a full loop doesn't help (it's the global maximum), answer is -1.
    
    Time: O(n)
    Space: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []
    
    for i in range(2 * n):
        while stack and nums[stack[-1]] < nums[i % n]:
            idx = stack.pop()
            result[idx] = nums[i % n]
        # Only push during the first pass (avoid duplicate pushes)
        if i < n:
            stack.append(i)
    
    return result


# Test
nums = [1, 2, 1]
print(next_greater_elements_circular(nums))  # [2, -1, 2]

nums = [1, 2, 3, 4, 3]
print(next_greater_elements_circular(nums))  # [2, 3, 4, -1, 4]

2.5 Complete Derivation for Largest Rectangle in Histogram

Let us rigorously derive the LeetCode #84 solution.

Formalization: Given heights[0..n-1], find max(heights[k] * (right[k] - left[k] - 1)), where:

• left[k] = index of the first bar to the left of k with height < heights[k] (or -1 if none)
• right[k] = index of the first bar to the right of k with height < heights[k] (or n if none)

Why does enumerating each bar as the height cover the optimal solution?

The optimal rectangle's height must equal the shortest bar within its range (otherwise you could lower the height without gaining width, so area wouldn't increase). Therefore, the optimal rectangle must be "using some bar's height, extended as far as possible in both directions." Enumerating all bars covers the optimal.

Two-pass solution (clearer conceptually):

def largest_rectangle_two_pass(heights: list[int]) -> int:
    """Two separate passes to compute left[] and right[], then one pass for max area."""
    n = len(heights)
    left = [-1] * n   # first shorter bar to the left
    right = [n] * n   # first shorter bar to the right
    
    # Left to right: monotone increasing stack for left[]
    stack = []
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    # Right to left: monotone increasing stack for right[]
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    # Compute maximum area
    max_area = 0
    for i in range(n):
        area = heights[i] * (right[i] - left[i] - 1)
        max_area = max(max_area, area)
    
    return max_area

One-pass solution (with sentinels, more efficient):

Key observation: When we pop element k from the monotone increasing stack, the element being pushed (i) is right[k], and the new stack top after popping is left[k]. A single pass simultaneously determines both boundaries!

This is the principle behind the sentinel version from Level 1. Sentinels eliminate "empty stack" checks and post-loop cleanup.

2.6 Template Summary

After the above analysis, we can distill two monotone stack templates:

Template 1: Find the first greater/smaller to the right

def find_right(nums, compare):
    """
    compare(a, b) determines what we're looking for:
    - compare = lambda a, b: a < b  → find next greater
    - compare = lambda a, b: a > b  → find next smaller
    """
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(n):
        while stack and compare(nums[stack[-1]], nums[i]):
            result[stack.pop()] = i  # or nums[i], depending on need
        stack.append(i)
    return result

Template 2: Find the first greater/smaller to the left

def find_left(nums, compare):
    """Left to right traversal; the stack top is the left boundary."""
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(n):
        while stack and compare(nums[stack[-1]], nums[i]):
            stack.pop()
        result[i] = stack[-1] if stack else -1
        stack.append(i)
    return result

Selection guide:

Level 3 · What the Theory Says

3.1 Monotone Stacks and Divide-and-Conquer: The Cartesian Tree

The Cartesian Tree was introduced by Jean Vuillemin in "A unifying look at data structures" (Communications of the ACM, 1980). It is a binary tree that simultaneously satisfies:

1. BST property: In-order traversal yields the original array order
2. Heap property: Each node's value is smaller (or larger) than its children's values

The stunning connection between Cartesian trees and monotone stacks:

A single linear scan with a monotone stack constructs exactly the Cartesian tree of the array!

def build_cartesian_tree(nums: list[int]):
    """
    Build a Cartesian tree (min-heap property) in O(n) using a monotone stack.
    
    Algorithm:
    1. Maintain a monotone increasing stack (values increase).
    2. When pushing a new element, pop all elements greater than it.
    3. The last popped element becomes the new element's left subtree.
    4. The new element becomes the right child of the current stack top.
    
    This matches the linear-time Cartesian tree construction described by
    Gabow, Bentley, and Tarjan (1984).
    """
    class Node:
        def __init__(self, val, idx):
            self.val = val
            self.idx = idx
            self.left = None
            self.right = None
    
    stack = []  # stores Nodes
    
    for i, num in enumerate(nums):
        node = Node(num, i)
        last_popped = None
        
        while stack and stack[-1].val > num:
            last_popped = stack.pop()
        
        node.left = last_popped  # last popped becomes left subtree
        
        if stack:
            stack[-1].right = node  # new node becomes right child of stack top
        
        stack.append(node)
    
    # Bottom of stack is the root
    return stack[0] if stack else None

Cartesian trees and the largest rectangle in histogram:

The histogram problem can be solved with divide-and-conquer:

1. Find the minimum heights[m] in range [l, r]
2. Rectangle area using m as height = heights[m] * (r - l + 1)
3. Recursively solve [l, m-1] and [m+1, r]

This divide-and-conquer structure corresponds exactly to the Cartesian tree of the heights array! Each tree node represents one divide step: the node's value is the interval minimum, left subtree is the left segment, right subtree is the right segment.

• If the Cartesian tree is balanced: recursion depth O(log n), total time O(n log n)
• If it degenerates (e.g., sorted array): depth O(n), total time O(n²)
• The monotone stack solution is always O(n), because it doesn't actually recurse—it completes all computations in a single sweep

Summary: The monotone stack can be viewed as "implicitly constructing the Cartesian tree." Divide-and-conquer works top-down on the tree; the monotone stack works left-to-right on the array. They compute the same thing, but the monotone stack avoids recursion overhead and worst-case degeneration.

3.2 Monotone Queue Optimization of Dynamic Programming

The most profound application of monotone queues isn't sliding window maximum—it's optimizing DP state transitions. When the DP recurrence has the form:

dp[i] = max/min { dp[j] + cost(j, i) }, where j ranges over a sliding window

the monotone queue can reduce each state computation from O(k) (window size) to amortized O(1).

Classic application: Bounded Knapsack (Multiple Knapsack) Optimization

Standard multiple knapsack: N item types, type i has volume vᵢ, value wᵢ, quantity sᵢ. Knapsack capacity V. Maximize total value.

Naive DP: dp[j] = max(dp[j - kv] + kw), k = 0, 1, ..., s. Complexity O(NVS).

Monotone queue optimization:

For a fixed item (volume v, value w, quantity s), group all capacities j by j mod v.

Within a group, let j = r + p*v (r is remainder, p = 0, 1, 2, ...), then:

dp[r + pv] = max { dp[r + kv] - kw } + pw, where max(0, p-s) ≤ k ≤ p

This is a sliding window maximum problem! Window size is s+1, and we maintain a monotone queue over dp[r + kv] - kw.

def multiple_knapsack_deque(N: int, V: int, items: list[tuple]) -> int:
    """
    Multiple Knapsack - monotone queue optimization
    items: [(volume, value, count), ...]
    
    Time: O(NV), significant improvement over naive O(NVS)
    Space: O(V)
    """
    dp = [0] * (V + 1)
    
    for vol, val, cnt in items:
        if vol == 0:
            continue
        for r in range(vol):
            dq = deque()  # (position p, dp[r+p*vol] - p*val)
            max_p = (V - r) // vol
            for p in range(max_p + 1):
                j = r + p * vol
                cur_val = dp[j] - p * val
                
                # Maintain decreasing monotone deque
                while dq and dq[-1][1] <= cur_val:
                    dq.pop()
                dq.append((p, cur_val))
                
                # Remove expired front
                if dq[0][0] < p - cnt:
                    dq.popleft()
                
                # Transition
                dp[j] = dq[0][1] + p * val
    
    return dp[V]

Other classic DP optimization scenarios:

1. Maximum subarray sum with length constraint: Find max sum subarray of length ≤ k. With prefix sums: max(prefix[i] - prefix[j]), j ∈ [i-k, i-1]. Maintain monotone increasing queue over prefix[j] (to find minimum).

2. Jump Game VII (LeetCode #1871): dp[i] = any(dp[j] for j in [i-maxJump, i-minJump]). Optimizable with monotone queue or prefix sums.

3. Frog Jump (USACO variants): dp[i] = min(dp[j]) + a[i], j ∈ [i-k, i-1]. Maintain monotone increasing queue over dp[j].

3.3 Amortized Analysis: Three Proofs That Monotone Stack is O(n)

Amortized analysis has three classic methods, systematized by Robert Tarjan in "Amortized Computational Complexity" (SIAM Journal on Algebraic and Discrete Methods, 1985). Let's prove the O(n) complexity of monotone stacks using all three.

Method 1: Aggregate Analysis

Instead of analyzing individual operation costs, analyze the total cost of n operations.

• Push executes exactly n times (each element pushed once)
• Pop executes at most n times (each element popped at most once)
• Total cost T(n) ≤ 2n
• Amortized cost per operation = T(n)/n = 2 = O(1)

Method 2: Accounting Method (Banker's Method)

Assign each operation an "amortized cost" (possibly above or below actual cost), ensuring the "bank balance" never goes negative.

• Each push: amortized cost = 2 (actual cost 1, save 1 "dollar" in the bank)
• Each pop: amortized cost = 0 (actual cost 1, withdraw 1 dollar from the bank)

Verification: Each element deposits 1 dollar when pushed. When it's popped, that dollar pays for the pop. Since each element is pushed at most once and popped at most once, the bank balance is always non-negative.

Total amortized cost = n × 2 = 2n = O(n).

Method 3: Potential Method (Physicist's Method)

Define potential function Φ(Dᵢ) = number of elements in the stack after the i-th operation.

Initial potential Φ(D₀) = 0, and Φ(Dᵢ) ≥ 0 (stack size is non-negative).

For the i-th operation:

• Let kᵢ elements be popped (kᵢ ≥ 0), then 1 element is pushed
• Actual cost: cᵢ = kᵢ + 1
• Potential change: ΔΦᵢ = Φ(Dᵢ) - Φ(Dᵢ₋₁) = 1 - kᵢ
• Amortized cost: ĉᵢ = cᵢ + ΔΦᵢ = (kᵢ + 1) + (1 - kᵢ) = 2

Regardless of kᵢ, the amortized cost is always 2.

Total cost = Σcᵢ = Σĉᵢ - (Φ(Dₙ) - Φ(D₀)) ≤ 2n - 0 = 2n = O(n).

Why do all three methods agree?

Because they describe the same fact differently. Aggregate analysis directly counts totals; the accounting method prepays costs at "cheap" operations; the potential method encodes "stored work" as potential. They all say: total pops are bounded by total pushes.

3.4 Historical Background and Theoretical Standing

The monotone stack as an algorithmic technique can be traced to these foundational works:

1. Largest rectangle in histogram: The earliest linear-time solution appears in work from the early 1990s, though the idea of using a stack for this problem dates back to 1980s computational geometry literature.

2. All Nearest Smaller Values problem: Berkman, Schieber, and Vishkin (1993) formalized "finding all nearest smaller values" as a standard problem in "Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values," providing parallel algorithms. The sequential version is precisely the monotone stack.

3. Cartesian tree construction: Vuillemin (1980) and Gabow, Bentley, Tarjan (1984) established the connection between monotone stacks and Cartesian trees.

In competitive programming, monotone stacks/queues became standard techniques through IOI/ACM contests in the 1990s, later entering the interview domain through platforms like LeetCode.

Level 4 · Edge Cases and Pitfalls

4.1 Trapping Rain Water: Four Complete Solutions Compared

LeetCode #42 — Trapping Rain Water is one of the highest-frequency interview problems. It has at least four distinct solution approaches, each embodying different algorithmic thinking.

Solution 1: Brute Force (O(n²) time, O(1) space)

def trap_brute(height: list[int]) -> int:
    """
    For each position i, find:
    - left_max: tallest bar to the left of i (inclusive)
    - right_max: tallest bar to the right of i (inclusive)
    Water at i = min(left_max, right_max) - height[i]
    
    Correctness: The water level at position i is determined by the shorter
    of the two tallest boundaries (bucket principle).
    """
    n = len(height)
    water = 0
    for i in range(n):
        left_max = max(height[:i + 1])
        right_max = max(height[i:])
        water += min(left_max, right_max) - height[i]
    return water

Solution 2: Prefix Maximum (O(n) time, O(n) space)

def trap_prefix(height: list[int]) -> int:
    """Precompute left_max[] and right_max[] to avoid redundant computation."""
    n = len(height)
    if n == 0:
        return 0
    
    left_max = [0] * n
    right_max = [0] * n
    
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])
    
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    return water

Solution 3: Monotone Stack (O(n) time, O(n) space)

(Shown in Level 1 — computes water layer by layer, row by row)

Solution 4: Two Pointers (O(n) time, O(1) space)

def trap_two_pointers(height: list[int]) -> int:
    """
    Two pointers is the space-optimized version of the prefix maximum approach.
    
    Key insight:
    - If left_max < right_max, position 'left' only depends on left_max
      (because a taller bar on the right guarantees containment)
    - Vice versa
    
    So we don't need to precompute two arrays. Two pointers move inward from
    both ends; each step moves the "shorter side."
    """
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    
    return water

Comparison of all four approaches:

Interview advice: Start with the O(n²) brute force idea, optimize to prefix max O(n)/O(n), then present two pointers O(n)/O(1). Mention the monotone stack version if asked. Demonstrating "iterative optimization" thinking is more impressive than jumping straight to the optimal solution.

4.2 Online Stock Span (LeetCode #901)

Problem: Design a class StockSpanner that receives a stock price each day and returns how many consecutive days (including today) the price has been ≤ today's price.

Example: prices = [100, 80, 60, 70, 60, 75, 85], output = [1, 1, 1, 2, 1, 4, 6]

This is essentially "find the first element to the left that is greater than the current"—how many consecutive smaller-or-equal values are there looking left.

class StockSpanner:
    """
    Stock Price Span - monotone decreasing stack
    
    Maintain a stack with strictly decreasing prices from bottom to top.
    Store (price, span) pairs where span = how many days this price "absorbed."
    
    When new price >= stack top price, pop and add its span to current span.
    
    Time: Amortized O(1) per call (O(n) total)
    Space: O(n)
    """
    
    def __init__(self):
        self.stack = []  # (price, span)
    
    def next(self, price: int) -> int:
        span = 1  # at least today itself
        
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack[-1][1]
            self.stack.pop()
        
        self.stack.append((price, span))
        return span


# Test
spanner = StockSpanner()
prices = [100, 80, 60, 70, 60, 75, 85]
for p in prices:
    print(spanner.next(p), end=' ')  # 1 1 1 2 1 4 6
print()

What makes this problem elegant: The stack stores (price, span) pairs rather than bare indices or values. When a price is popped, its span is merged into the new element. The new element effectively "absorbs" all shorter historical records.

Common mistakes:

• Using < instead of <=: The problem says "less than or equal to today," so equal values should also be popped
• Forgetting to count today itself (span initialized to 1, not 0)

4.3 Maximal Rectangle (LeetCode #85, Building on #84)

Problem: Given a 2D binary matrix containing only '0' and '1', find the area of the largest rectangle containing only '1'.

Key insight: Treat each row as the "ground level," count consecutive 1's upward as bar heights, transforming the 2D problem into multiple 1D histogram problems.

def maximal_rectangle(matrix: list[list[str]]) -> int:
    """
    Maximal Rectangle - built on LeetCode #84
    
    Approach:
    1. Build a histogram row by row: heights[j] = consecutive 1's above current row
    2. For each row's histogram, call largest_rectangle_area
    
    Time: O(m * n), where m = rows, n = columns
    Space: O(n)
    """
    if not matrix or not matrix[0]:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    heights = [0] * n
    max_area = 0
    
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == '1':
                heights[j] += 1
            else:
                heights[j] = 0  # bar breaks on '0'
        
        max_area = max(max_area, largest_rectangle_area_helper(heights))
    
    return max_area


def largest_rectangle_area_helper(heights: list[int]) -> int:
    """Same as Level 1 implementation."""
    heights_ext = [0] + heights + [0]
    stack = [0]
    max_area = 0
    
    for i in range(1, len(heights_ext)):
        while heights_ext[i] < heights_ext[stack[-1]]:
            h = heights_ext[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, h * width)
        stack.append(i)
    
    return max_area


# Test
matrix = [
    ['1', '0', '1', '0', '0'],
    ['1', '0', '1', '1', '1'],
    ['1', '1', '1', '1', '1'],
    ['1', '0', '0', '1', '0']
]
print(maximal_rectangle(matrix))  # 6

Row-by-row histogram evolution:

Row 0: heights = [1, 0, 1, 0, 0] → max rectangle = 1
Row 1: heights = [2, 0, 2, 1, 1] → max rectangle = 3
Row 2: heights = [3, 1, 3, 2, 2] → max rectangle = 6  ← global max
Row 3: heights = [4, 0, 0, 3, 0] → max rectangle = 4

At row 2, heights = [3, 1, 3, 2, 2]. Using height 2, we can span indices 2-4: area = 2*3 = 6.

4.4 Strict vs. Non-Strict Monotonicity

This is the most error-prone aspect of monotone stacks. The difference between < and <= leads to completely different behavior.

Scenario analysis:

Consider "next greater element" for array [5, 5, 5, 3]:

1. Strict monotone decreasing stack (pop condition stack[-1] < nums[i]):

   • Equal elements don't trigger pops; they all stay in the stack
   • All three 5's remain in the stack; their "next greater" is -1
   • Correct! There truly is nothing "greater"

2. Non-strict monotone decreasing stack (pop condition stack[-1] <= nums[i]):

   • Equal elements also get popped
   • First 5 gets popped when second 5 arrives, result[0] = 5
   • Wrong! 5 is not greater than 5

Rule:

• Finding "strictly greater/smaller": use < / > as pop condition
• Finding "greater-or-equal / smaller-or-equal": use <= / >= as pop condition

Special case in largest rectangle in histogram:

heights = [2, 2, 2], correct answer is 6 (three bars form a 2×3 rectangle).

With strict monotonicity (heights[stack[-1]] > heights[i] to pop):

• Three equal 2's don't trigger pops, stack = [0, 1, 2]
• When the right sentinel pops them:
  • Pop 2: width = 3 - 1 - 1 = 1, area = 2
  • Pop 1: width = 3 - 0 - 1 = 2, area = 4
  • Pop 0: width = 3 - (-1) - 1 = 3, area = 6 ✓

With non-strict (heights[stack[-1]] >= heights[i] to pop):

• Second 2 pops the first: more complex reasoning, but ultimately also correct

Conclusion: In the histogram problem, both approaches give correct results, but the reasoning differs. Recommend using >= (non-strict) + sentinels—the safest combination.

4.5 When to Use Monotone Stack vs. Priority Queue (Heap)

Both find "max/min," but suit different scenarios:

Decision criteria:

1. Does the problem have "directionality"? Processing array elements sequentially, finding the first in some direction satisfying a condition → monotone stack
2. Need a global extremum? Need the max/min of all current data at any time → heap
3. Fixed-size sliding window? Only need max/min → monotone queue (O(n)) beats heap (O(n log n))
4. Need the kth largest? → heap (monotone stack/queue can't do Top-K)

Hybrid scenarios:

Some problems require both. For example, "Find Median from Data Stream" (LeetCode #295) uses two heaps, but "Sliding Window Median" (LeetCode #480) requires more sophisticated structures (sorted containers or deletable heaps).

4.6 Interview Strategy

Identifying monotone stack problems:

1. The problem asks for "next greater/smaller" or "previous greater/smaller"
2. The problem involves "left and right boundaries" (histogram, rain water)
3. The problem reduces to "for each element, find the first in some direction satisfying a condition"
4. You see an O(n²) brute force where each element scans in one direction

Communication template for interviews:

"The brute force scans rightward from each element to find the first greater value: O(n²). But we observe that if B > A and B is to A's right, then B can also 'help' elements to A's left that are smaller than B. Exploiting this transitivity, we use a monotone stack—maintain a decreasing stack, and when a new element arrives, pop everything smaller. Each popped element has found its answer. Every element is pushed and popped exactly once: O(n) total."

High-frequency interview problem list:

4.7 Bonus Problem: Sum of Subarray Minimums (LeetCode #907)

This problem showcases an important application pattern of monotone stacks — the contribution method.

Problem: Given array arr, find the sum of minimums of all subarrays. Return the result modulo 10⁹+7.

Brute force: Enumerate all O(n²) subarrays, find minimum of each: O(n³) or O(n²).

Monotone stack + contribution method: For each arr[i], compute how many subarrays have it as their minimum.

If arr[i] is the minimum in range [left, right], the number of subarrays containing i and staying within [left, right] = (i - left) * (right - i).

def sum_subarray_mins(arr: list[int]) -> int:
    """
    Sum of Subarray Minimums - monotone stack + contribution method
    
    For each arr[i], find:
    - left[i]: first strictly smaller element to the left (index, or -1)
    - right[i]: first less-than-or-equal element to the right (index, or n)
    
    Note: left and right handle equal elements DIFFERENTLY!
    This avoids double-counting: for equal elements, we assign "ownership"
    (e.g., "leftmost among equals owns the subarray") by using strict < on
    one side and <= on the other.
    
    Number of subarrays where arr[i] is minimum = (i - left[i]) * (right[i] - i)
    Contribution = arr[i] * (i - left[i]) * (right[i] - i)
    """
    MOD = 10**9 + 7
    n = len(arr)
    
    # left[i]: first strictly smaller to the left, or -1
    left = [-1] * n
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:  # >= means equal gets popped
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    # right[i]: first less-than-or-equal to the right, or n
    right = [n] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:  # > means equal stays
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    # Compute total contribution
    result = 0
    for i in range(n):
        result += arr[i] * (i - left[i]) * (right[i] - i)
        result %= MOD
    
    return result


# Test
arr = [3, 1, 2, 4]
print(sum_subarray_mins(arr))  # 17
# Subarrays: [3]=3, [1]=1, [2]=2, [4]=4, [3,1]=1, [1,2]=1, [2,4]=2,
#            [3,1,2]=1, [1,2,4]=1, [3,1,2,4]=1
# Sum = 3+1+2+4+1+1+2+1+1+1 = 17

Why handle equal elements differently on left vs. right?

Consider arr = [1, 1, 1]. Subarray [1,1,1] has minimum 1—this contribution should be counted exactly once. If both sides use strict <, all three positions would "claim" responsibility for this subarray, causing overcounting.

Solution: Define an "ownership rule." For instance, "among equal elements, the leftmost one owns the subarray":

• left uses >= (equal gets popped → seeking strictly smaller boundary)
• right uses > (equal stays → seeking less-than-or-equal boundary)

This way, among consecutive equal elements, only the leftmost one has the largest "responsibility range."

4.8 Summary and Intuition Map

                Monotone Stack/Queue Knowledge Map
                    
    ┌─────────────────────────────────────────────┐
    │             Application Problems             │
    │  ┌──────┐  ┌──────┐  ┌──────┐  ┌──────┐   │
    │  │ NGE  │  │ Rain │  │Rect. │  │Slide │   │
    │  │ #496 │  │ #42  │  │ #84  │  │ #239 │   │
    │  └──┬───┘  └──┬───┘  └──┬───┘  └──┬───┘   │
    └─────┼─────────┼─────────┼─────────┼────────┘
          │         │         │         │
          v         v         v         v
    ┌─────────────────────────────────────────────┐
    │          Core Data Structures                │
    │                                              │
    │  Decreasing stack   Increasing stack  Deque  │
    │  (find greater)     (find smaller)  (window) │
    └──────────────────────┬──────────────────────┘
                           │
                           v
    ┌─────────────────────────────────────────────┐
    │           Underlying Theory                  │
    │                                              │
    │  Amortized O(n)   Cartesian tree  DP optim.  │
    │  (potential)      (divide equiv.) (knapsack) │
    └─────────────────────────────────────────────┘

Memory mnemonic:

Monotone stack finds neighbors — the first greater/smaller in each direction. Monotone queue watches windows — who's the max/min inside. Each element enters once, leaves once — linear time, no surprise. Add sentinels to kill edge cases; strict vs. non-strict, choose with care.

Exercises

Fundamentals (Level 1-2)

1. Implement LeetCode #496 using a monotone stack + hash map.
2. Implement LeetCode #739 to compute waiting days for warmer temperatures.
3. Implement LeetCode #239 using a monotone queue.
4. Compare the prefix-max and two-pointer solutions for #42. Hand-trace [4,2,0,3,2,5].

Advanced (Level 3-4)

5. Implement LeetCode #84 two ways (two-pass vs. sentinel one-pass) and compare.
6. Implement LeetCode #85, building on #84.
7. Implement LeetCode #907, paying attention to handling equal elements.
8. Using the potential method, prove: if each element can be pushed at most 2 times (as in circular array with two passes), is the total complexity O(n) or O(2n)?

Thought Questions

9. Why doesn't the two-pointer approach for trapping rain water need a stack? What mathematical property guarantees its correctness?
10. If an interviewer demands O(1) space for #84 (largest rectangle in histogram), is it possible? Why or why not?