Monotonic Stack

monotonic-stack: The Ultimate Cheatsheet

1. Detailed Explanation

A monotonic stack is a stack data structure that maintains a strictly increasing (or decreasing) order of elements. Unlike a regular stack (LIFO), a monotonic stack enforces an ordering constraint on its elements. This constraint allows for efficient processing of problems involving finding the nearest smaller (or larger) element for each element in a sequence.

Why is it important? Monotonic stacks are particularly useful for solving problems that require finding the next smaller/larger element, or the range of elements that are smaller/larger than a given element. These problems often appear in array processing, signal processing, and other areas where relative element magnitudes are crucial.

Core Concepts:

• Monotonicity: The key property. Elements are added and removed to maintain either strictly increasing or strictly decreasing order.
• Stack Operations: push() and pop() operations are used to maintain the monotonic order. Crucially, elements might be popped before pushing a new element to enforce monotonicity.
• Nearest Smaller/Larger Element: The primary application is finding the nearest element on either side that is smaller or larger than a given element.

2. When to Use monotonic-stack (and When Not To)

Use Monotonic Stack when:

• You need to find the nearest smaller/larger element to the left or right of each element in an array.
• You need to determine the maximum/minimum area under a histogram (or similar shape).
• You need to find the largest rectangular area in a histogram.
• You’re dealing with problems involving range queries based on element comparisons.

Don’t use Monotonic Stack when:

• The problem can be efficiently solved using other data structures (e.g., a simple array, a heap, or a segment tree).
• The order of elements is irrelevant to the problem’s solution.
• The problem involves complex relationships between elements that go beyond simple comparisons.

3. Core Algorithm / Data Structure Template

1. Initialize an empty stack.
2. Iterate through the input array: a. While the stack is not empty and the current element violates the monotonic order (e.g., smaller than the top element in an increasing stack), pop elements from the stack and process them (e.g., calculate the nearest smaller element). b. Push the current element onto the stack.
3. Process any remaining elements in the stack. (These are the elements without a larger/smaller element to their right/left).

4. Code Implementations

Python

def nearest_smaller_to_right(arr):
    """Finds the nearest smaller element to the right for each element in an array."""
    stack = []
    result = []
    for i in range(len(arr) - 1, -1, -1):
        while stack and stack[-1] >= arr[i]:
            stack.pop()
        if stack:
            result.insert(0, stack[-1])  # Insert at beginning to maintain order
        else:
            result.insert(0, -1)  # No smaller element to the right
        stack.append(arr[i])
    return result

Java

import java.util.Stack;
import java.util.ArrayList;
import java.util.List;

public class MonotonicStack {
    public static List<Integer> nearestSmallerToRight(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        for (int i = arr.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() >= arr[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                result.add(0, stack.peek());
            } else {
                result.add(0, -1);
            }
            stack.push(arr[i]);
        }
        return result;
    }
}

C++

#include <iostream>
#include <vector>
#include <stack>

std::vector<int> nearestSmallerToRight(const std::vector<int>& arr) {
    std::stack<int> s;
    std::vector<int> result;
    for (int i = arr.size() - 1; i >= 0; --i) {
        while (!s.empty() && s.top() >= arr[i]) {
            s.pop();
        }
        if (!s.empty()) {
            result.insert(result.begin(), s.top());
        } else {
            result.insert(result.begin(), -1);
        }
        s.push(arr[i]);
    }
    return result;
}

5. Complexity Analysis

Operation	Time Complexity (Best/Average/Worst)	Space Complexity (Worst)
push()	O(1) / O(1) / O(n)	O(n)
pop()	O(1) / O(1) / O(1)	O(n)
Nearest Smaller	O(n)	O(n)

The worst-case time complexity occurs when the input array is already monotonically increasing (or decreasing), resulting in all elements being pushed onto the stack before any pops occur.

6. Pro Tips, Tricks, and Common Pitfalls

• Choosing Monotonicity: Carefully decide whether you need an increasing or decreasing stack based on the problem’s requirements (e.g., finding the nearest smaller element requires a decreasing stack).
• Edge Cases: Handle empty stacks and arrays appropriately. Consider what to return when there’s no smaller/larger element to the left/right.
• Off-by-One Errors: Pay attention to array indices and loop boundaries to avoid off-by-one errors, especially when processing the remaining stack elements.
• Debugging: Use a debugger or print statements to trace the stack’s contents during execution to help understand its behavior.

7. Classic Problem Examples

Example: Trapping Rain Water

Description: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

High-Level Approach:

Use two monotonic stacks: one for increasing heights from the left, and one for increasing heights from the right. For each bar, find the maximum height to its left and right using the stacks. The trapped water for that bar is the minimum of these maximum heights minus the bar’s height. Sum the trapped water for all bars. This approach avoids redundant calculations compared to a brute-force approach. A single monotonic stack can also be used with some modifications.