Monotonic Stack — Equal-Price Operator Off-by-One

The monotonic stack is one of the most underrated patterns in algorithm interviews. I've watched engineers spend 45 minutes brute-forcing problems in O(n²) when the monotonic stack gives O(n) in 15 minutes of clean code. Once you internalise the pattern, you'll spot it in problems that don't obviously look like a stack problem — and that recognition is what separates strong algorithm interviewers from average ones. Don't underestimate it: get the direction wrong and you're debugging for half an hour.

What Is a Monotonic Stack?

A monotonic stack is a stack that maintains its elements in monotonically increasing or decreasing order. The invariant is enforced during push: before pushing a new element, pop all elements that violate the desired order. This guarantees that at any point, the stack is sorted.

The key insight: each element is pushed once and popped at most once, giving linear time regardless of how many elements get popped in a single step.

Monotonic stacks excel at problems that ask for the next or previous greater/smaller element — especially when you need to compute distances, spans, or areas based on those relationships.

Production news: you'll find this pattern in stock market analysis, weather data processing, and even in some database query optimisers. It's not just LeetCode theory.

Monotonic Decreasing Stack — Next Greater Element

The classic problem: given an array, for each element find the next element to its right that is strictly greater. Brute force is O(n²). Monotonic stack is O(n) — each element is pushed and popped at most once.

The invariant: the stack always holds indices of elements in decreasing order of value. When we see a new element larger than the stack top, that top has found its 'next greater' answer.

Here's a Python implementation, plus a Java version to show language independence.

from typing import List

def next_greater_element(nums: List[int]) -> List[int]:
    """
    For each element, find the next strictly greater element to its right.
    Returns -1 if none exists.

    Approach: monotonic decreasing stack of indices.
    When a new element is greater than the stack top, the top has found its answer.

    Time:  O(n) — each element pushed/popped at most once
    Space: O(n) — stack + result array
    """
    n = len(nums)
    result = [-1] * n
    stack = []          # indices, maintained in decreasing order of nums[index]

    for i in range(n):
        # While current element beats the stack top:
        # the top's 'next greater' is nums[i]
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    # Remaining indices in stack → no greater element → stay -1

    return result


print(next_greater_element([2, 1, 2, 4, 3]))
# [4, 2, 4, -1, -1]
# Trace:
# i=0: push 0. stack=[0]  (val=2)
# i=1: 1<2 → push 1. stack=[0,1]
# i=2: 2>1 → pop 1, result[1]=2. 2==2 → push 2. stack=[0,2]
# i=3: 4>2 → pop 2, result[2]=4. 4>2 → pop 0, result[0]=4. push 3. stack=[3]
# i=4: 3<4 → push 4. stack=[3,4]
# End: indices 3,4 remain → result[3]=result[4]=-1


def stock_span(prices: List[int]) -> List[int]:
    """
    Stock Span: for each day, how many consecutive previous days
    (including today) had price <= today's price?

    Monotonic decreasing stack of (index, price) pairs.
    Time: O(n), Space: O(n)
    """
    span = [0] * len(prices)
    stack = []   # (index, price) in decreasing price order

    for i, price in enumerate(prices):
        while stack and price >= stack[-1][1]:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1][0]
        stack.append((i, price))

    return span

print(stock_span([100, 80, 60, 70, 60, 75, 85]))
# [1, 1, 1, 2, 1, 4, 6]

Monotonic Increasing Stack — Next Smaller Element and Largest Rectangle

Flip the comparison direction and you get the monotonic increasing stack — elements in the stack are always in increasing order. Pop when the current element is smaller than the top. Use for 'next smaller element' problems.

The Largest Rectangle in Histogram is the canonical hard problem that uses this pattern.

Key insight: when you pop a bar, you know its right boundary (current index) and its left boundary (the new stack top after pop). The width is the difference. This gives O(n) instead of O(n²).

from typing import List

def next_smaller_element(nums: List[int]) -> List[int]:
    """
    Monotonic INCREASING stack.
    For each element, find the next strictly smaller element to its right.
    Time: O(n), Space: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []   # indices in increasing order of nums[index]

    for i in range(n):
        while stack and nums[i] < nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

print(next_smaller_element([4, 2, 3, 1, 5]))
# [2, 1, 1, -1, -1]


def largest_rectangle_histogram(heights: List[int]) -> int:
    """
    Largest rectangle in histogram.
    Classic monotonic increasing stack problem.
    Time: O(n), Space: O(n)

    Key insight: when we pop a bar because the current bar is shorter,
    we know the FULL width that popped bar can extend to.
    """
    max_area = 0
    stack = []   # (start_index, height) — monotonic increasing by height
    heights = heights + [0]   # sentinel 0 forces all remaining bars to pop

    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            width    = i - idx
            max_area = max(max_area, height * width)
            start    = idx   # This bar can extend back to where the popped bar started
        stack.append((start, h))

    return max_area

print(largest_rectangle_histogram([2, 1, 5, 6, 2, 3]))
# 10  (bars of height 5 and 6 form a 2-wide × 5-tall = 10 rectangle)

Variations and Nuances

Common nuance: strict vs non-strict comparisons. For example, 'next greater element' typically uses strict >, but 'next greater or equal' requires >=. Misunderstanding this shifts the output by one position.

Here's the rain water snippet — notice it's the same decreasing stack pattern with index arithmetic.

def trap(heights: List[int]) -> int:
    """
    Trapping rain water using monotonic decreasing stack.
    Time: O(n), Space: O(n)
    """
    water = 0
    stack = []  # indices, decreasing heights
    for i, h in enumerate(heights):
        while stack and h > heights[stack[-1]]:
            bottom_idx = stack.pop()
            if not stack:
                break
            left_idx = stack[-1]
            width = i - left_idx - 1
            height = min(heights[left_idx], h) - heights[bottom_idx]
            water += width * height
        stack.append(i)
    return water

Implementation Pitfalls and Debugging

Even with the algorithm correct, monotonic stack implementations have common bugs: 1. Storing values instead of indices — you need indices to compute distances, spans, and widths. 2. Off-by-one in sentinel — sentinel should be at the end (not beginning), and its value must be small enough (0 for increasing stack, large for decreasing). 3. Incorrect update of start index in Largest Rectangle — when popping, the new bar's start must be set to the popped bar's start to extend width.

Debugging these often starts with printing the stack at each iteration and verifying invariants. Use print(f'stack: {stack}') with indices, and trace with a tiny array like [2,1,2].

Here's a debug trace for the NGE example:

def debug_nge(nums):
    n, res = len(nums), [-1]*len(nums)
    stack = []
    for i in range(n):
        print(f'i={i}, val={nums[i]}, stack_before={stack}')
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            res[idx] = nums[i]
            print(f'  pop {idx}, set res[{idx}]={nums[i]}, stack={stack}')
        stack.append(i)
        print(f'  push {i}, stack_after={stack}')
    print(f'final res: {res}')
    return res

debug_nge([2,1,2,4,3])

Real-World Applications: Beyond LeetCode

In each case, the pattern is the same: iterate a sequence, maintain a monotonic structure, and use the pop event to compute something about the relationship between elements.

Think of it as a 'delayed answer' pattern — elements wait until a later element determines their fate.

Why Monotonic Stacks Beat Nested Loops Every Time

When you reach for a nested loop to find the next greater element, you're writing O(n²) code that will fail at scale. A monotonic stack collapses that to O(n) by exploiting a simple invariant: each element enters and leaves the stack exactly once.

The insight isn't the stack itself — it's that you can discard elements the moment they become irrelevant. In the Next Greater Element problem, if you're processing left to right and element X has already found its greater element, keeping X around only slows you down. Pop it. Move on.

This pattern repeats across dozens of LeetCode problems because the underlying geometry is identical: you're searching for the first element that breaks some monotonic property. The stack just tracks which candidates are still alive. When the breaker arrives, the stack tells you exactly whose answer just got resolved.

Stop thinking of it as a data structure problem. It's an elimination problem. The stack is just your death tracker.

// io.thecodeforge — dsa tutorial

int[] findNextGreater(int[] prices) {
    int[] result = new int[prices.length];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < prices.length; i++) {
        while (!stack.isEmpty() && prices[stack.peek()] < prices[i]) {
            result[stack.pop()] = prices[i];
        }
        stack.push(i);
    }
    return result;
}

Tuning the Monotonic Direction to Match Your Query

Choosing increasing vs decreasing isn't random — it depends entirely on what you're looking for. If you need the next larger element, you want a decreasing stack (largest at bottom, smallest at top). When a bigger element arrives, everything smaller on top pops and gets its answer.

Flip it for next smaller element. An increasing stack (smallest at bottom) ensures that when a smaller element appears, the larger ones above finally get their resolution.

The most common mistake? Building the wrong polarity and wondering why nothing works. Trace through one pass manually. If the stack never pops, you've inverted the comparison operator.

Largest Rectangle in Histogram exploits this with a twist: you don't just pop on smaller heights — you need both the next smaller element to the left and right. Two passes, or one pass with index tracking. Same stack, just smarter bookkeeping.

Get the direction right first. Everything else is index arithmetic.

// io.thecodeforge — dsa tutorial

int largestRectangleInHistogram(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;
    
    for (int i = 0; i <= heights.length; i++) {
        int h = (i == heights.length) ? 0 : heights[i];
        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

Reading Stack State: What the Indices Really Tell You

Most tutorials show you elements. Production code needs indices. When you store indices instead of values, you recover both the value (via array lookup) and the distance between elements — critical for subarray problems.

Consider the sum of minimums of all subarrays problem. You can't just find the next smaller element; you need to know how many subarrays each element dominates. That requires left span and right span — both derived from index differences at pop time.

The stack's internal order also carries meaning. During processing, elements still on the stack haven't found their next greater element yet. They're the unlucky ones — descending peaks that nothing bigger has overtaken. In stock trading terms, they're the positions still underwater.

When you understand that the stack is storing unresolved futures, the whole pattern clicks. You're not just pushing and popping. You're resolving debts. Each pop is a liability settled. Each final leftover is a default.

That mental model makes the monotonic stack intuitive, not mechanical.

// io.thecodeforge — dsa tutorial

int sumSubarrayMins(int[] arr) {
    Deque<Integer> stack = new ArrayDeque<>();
    long sum = 0;
    int mod = 1_000_000_007;
    
    for (int i = 0; i <= arr.length; i++) {
        while (!stack.isEmpty() && (i == arr.length || arr[stack.peek()] > arr[i])) {
            int idx = stack.pop();
            int left = stack.isEmpty() ? -1 : stack.peek();
            int right = i;
            long count = (long)(idx - left) * (right - idx);
            sum = (sum + arr[idx] * count) % mod;
        }
        stack.push(i);
    }
    return (int)sum;
}

The Sliding Window Monotonic Stack: Max/Min of Every K-Sized Subarray

Most devs think monotonic stacks only handle "next greater element" queries. That's a rookie mistake. The real power shows up when you pair a monotonic stack with a sliding window — you get O(n) solutions for problems that scream for a deque but don't need one.

The trick: instead of pushing every element blindly, you maintain a strictly decreasing stack for max queries (or increasing for min). Before pushing a new element, pop from the back until the stack is monotonic again. Then trim expired indices from the front. The first element in the stack is always your window's answer. No heap, no nested loops, no bullshit.

This pattern kills problems like "Sliding Window Maximum" where naive solutions hit O(n*k). Production streaming pipelines and real-time analytics use this exact technique to maintain running statistics on unbounded data. Understand the indices, and you own the window.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class SlidingWindowMax {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peekLast()] <= nums[i]) {
                stack.pollLast();
            }
            stack.offerLast(i);
            if (stack.peekFirst() <= i - k) {
                stack.pollFirst();
            }
            if (i >= k - 1) {
                result[i - k + 1] = nums[stack.peekFirst()];
            }
        }
        return result;
    }
}

Offline Queries: Precomputing the Monotonic State for Reuse

Stop running the same monotonic stack scan five times for five different queries. If your problem gives you a static array and asks multiple questions about "next greater" or "previous smaller," build the monotonic stack once and reuse the precomputed mappings.

Here's the senior approach: first pass builds a HashMap<Integer, Integer> for nextGreater given each index. Second pass builds previousSmaller. Now any query — "what's the next greater element after index 4?" — is O(1) lookups. You pay O(n) upfront and laugh at nested loops later.

This is exactly how database query optimizers work: they precompute index structures once and reuse them across query plans. Stop recomputing state. Build once, query many. The monotonic stack is your ETL pipeline — run it once and cache the results. Your future self will send you a beer.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class PrecomputedMonotonic {
    public static Map<Integer, Integer> nextGreater(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = arr.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= arr[i]) {
                stack.pop();
            }
            map.put(i, stack.isEmpty() ? -1 : stack.peek());
            stack.push(arr[i]);
        }
        return map;
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 7, 3, 5, 4, 6, 8};
        Map<Integer, Integer> ng = nextGreater(arr);
        System.out.println(ng.get(0)); // 7
        System.out.println(ng.get(2)); // 5
    }
}