Mastering Monotonic Stacks: Next Greater Element and Histogram Problems

Introduction

When designing algorithms to process sequential data, developers frequently encounter problems that require finding the relationship between an element and its surrounding elements—specifically, finding the next greater, previous smaller, or boundary limits within an array. A naive nested-loop approach yields an $O(N^2)$ time complexity, which is unacceptable for large datasets.

By leveraging a specialized data structure known as the Monotonic Stack, we can reduce these problems to an optimal $O(N)$ time complexity. This article explores the theoretical foundations of monotonic stacks, dissects their invariants, and walks through production-grade implementations for classic problems like Daily Temperatures and Largest Rectangle in Histogram.

Core Principles: What is a Monotonic Stack?

A monotonic stack is simply a standard stack data structure whose elements maintain a specific sorted order—either strictly increasing or strictly decreasing—from the bottom of the stack to the top.

There are two primary flavors:

1. Monotonic Increasing Stack: Elements are ordered in ascending order from bottom to top. Pushing a new element requires popping all elements greater than it.
2. Monotonic Decreasing Stack: Elements are ordered in descending order from bottom to top. Pushing a new element requires popping all elements smaller than it.

The magic of the monotonic stack lies in its popping invariant. As we iterate through an array, each element is pushed onto the stack at most once and popped at most once. This amortized analysis guarantees an $O(N)$ time complexity.

Problem 1: Next Greater Element (Daily Temperatures)

Problem Statement

Given an array of integers temperatures representing daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the $i$-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Algorithmic Approach

We need to find the next greater element for every index in the array. A monotonic decreasing stack is the ideal tool here.

• We iterate through the array from left to right.
• While the stack is not empty and the current temperature is strictly greater than the temperature at the index stored at the top of the stack, we pop from the stack.
• The difference between the current index and the popped index gives the number of days waited.
• Finally, we push the current index onto the stack.

Python Implementation

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # Stores indices of the temperatures array

    for i in range(n):
        # Pop elements from stack while current temperature is greater
        # than the temperature at the index stored at the top of the stack.
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_index = stack.pop()
            answer[prev_index] = i - prev_index

        # Push current index onto the stack to maintain decreasing order
        stack.append(i)

    return answer

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$. Each element is pushed and popped from the stack exactly once.
• Space Complexity: $\mathcal{O}(N)$ in the worst-case scenario (e.g., a strictly descending array of temperatures where all indices are stored in the stack).

Problem 2: Largest Rectangle in Histogram

Problem Statement

Given an array of integers heights representing the histogram's bar height where the width of each bar is $1$, return the area of the largest rectangle in the histogram.

Algorithmic Approach

For any given bar $i$, the maximum rectangle it can form is bounded by the first shorter bar to its left and the first shorter bar to its right.

To find these boundaries efficiently, we use a monotonic increasing stack:

1. We iterate through the histogram bars.
2. When we encounter a bar shorter than the bar at the stack's top, it means the bar at the stack's top has found its right boundary (the current index). Its left boundary is the new top of the stack after popping.
3. We compute the area for the popped bar and update our maximum area.
4. A common technique to flush out remaining elements is appending a sentinel value of 0 at the end of the heights array.

Java Implementation

import java.util.Stack;

public class HistogramSolution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            // Use 0 as a sentinel height at the end to process remaining stack elements
            int currentHeight = (i == n) ? 0 : heights[i];

            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                // If stack is empty, width spans from 0 to i
                // Otherwise, width spans between current index and the new stack top
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }

        return maxArea;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$. Every bar is pushed and popped exactly once during the traversal.
• Space Complexity: $\mathcal{O}(N)$ to store the indices in the stack.

Recognizing Monotonic Stack Patterns

When reviewing algorithmic challenges, look for the following indicator phrases to determine if a monotonic stack is applicable:

• "Next greater element" or "Previous smaller element"
• "Span of consecutive elements" (e.g., stock span problems)
• "Bounding limits" or "Boundary constraints affecting contiguous subarrays"

Problem Type	Stack Order	Popping Condition	Target Output
Next Greater	Decreasing	current > stack.peek()	Distance to next greater element
Next Smaller	Increasing	current < stack.peek()	Distance to next smaller element
Previous Greater	Decreasing	current >= stack.peek()	Bounding index to the left

Conclusion

Monotonic stacks are an indispensable weapon in a software engineer's algorithmic toolkit. By shifting our perspective from brute-force scanning to maintaining structural invariants during iteration, problems that initially appear quadratic in complexity drop cleanly into linear time. Practice identifying the invariants in boundary problems, and you will find monotonic stacks naturally applicable across a wide array of technical scenarios.