Monotonic Stack Technique

Description

For every element, find the next element to its right that is larger. Checking everything to the right of each element is O(n^2). But an element that has been beaten by a larger one to its right can never be the answer for anything further left - so it can be thrown away, and the survivors form a stack in sorted order.

This skill covers the monotonic stack: one pass that keeps only the candidates that can still be an answer, giving next greater or smaller elements in O(n). It also covers the contribution trick built on it, where each element's span as the minimum turns sums over all subarrays into one pass.

We'll go from simple to more technical:

1. The pattern: next greater element, popping everything the current element beats.
2. A second flavor: previous and next smaller spans, and each element's contribution.
3. Where it shows up (days until warmer, stock span, window statistics).
4. What breaks it: the duplicate rule, double-counted ties, sentinels, the O(n^2) illusion.

The approach

int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();        // candidates, increasing from top to bottom
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() <= nums[i]) {
            stack.pop();                              // not greater than nums[i]: useless for everything further left
        }
        result[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return result;
}

def next_greater_element(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack = []                                     # candidates, increasing from top to bottom
    for i in range(n - 1, -1, -1):
        while stack and stack[-1] <= nums[i]:
            stack.pop()                            # not greater than nums[i]: useless for everything further left
        result[i] = stack[-1] if stack else -1
        stack.append(nums[i])
    return result

Scanning right to left, the stack holds the candidates for "next greater" in increasing order from top to bottom. Anything not greater than nums[i] is popped: nums[i] is closer and at least as large, so it will block it for every earlier element. Each element is pushed once and popped at most once - O(n) in total, though the loops look nested. The pop condition decides duplicates: <= makes "greater" strict (the next greater of the first 2 in [2, 2, 3] is 3); popping only < would wrongly report 2.

Two common variants follow the same shape. Next smaller: flip the comparison. Stock span (how many consecutive days up to today had a price <= today's) scans left to right and keeps (price, span) pairs: pop every pair with price <= today's and add its span to today's.

A second flavor: count what each element is the minimum of

The previous and next smaller elements tell you the whole stretch where an element is the minimum. That turns several problems into "for each element, add up its contribution":

long sumSubarrayMins(int[] arr) {
    int n = arr.length;
    int[] left = new int[n], right = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {                     // previous STRICTLY smaller
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) stack.pop();
        left[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
    }
    stack.clear();
    for (int i = n - 1; i >= 0; i--) {                // next smaller OR EQUAL
        while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) stack.pop();
        right[i] = stack.isEmpty() ? n : stack.peek();
        stack.push(i);
    }
    long sum = 0;
    for (int i = 0; i < n; i++) sum += (long) arr[i] * (i - left[i]) * (right[i] - i);
    return sum;
}

def sum_subarray_mins(arr: list[int]) -> int:
    n = len(arr)
    left, right = [-1] * n, [n] * n
    stack = []
    for i in range(n):                             # previous STRICTLY smaller
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    stack.clear()
    for i in range(n - 1, -1, -1):                 # next smaller OR EQUAL
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    return sum(arr[i] * (i - left[i]) * (right[i] - i) for i in range(n))   # Python ints: no overflow

arr[i] is the minimum of every subarray that starts after left[i] and ends before right[i]: (i - left[i]) x (right[i] - i) of them. With equal values, one side must be strict and the other not, so a subarray whose minimum appears twice is credited to exactly one of them - with both sides strict, [1, 1] sums to 4 instead of 3. The same spans answer "maximum of minimums for every window size": element i is the minimum of a window of length right[i] - left[i] - 1, and a best value for a longer window is also achievable for every shorter one.

Where you'll see it

"How many days until a warmer day", "the next price higher than today's" and trading indicators like the stock span are next-greater problems over time series. Contribution counting appears in analytics that sum a statistic over every time window without enumerating the windows.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why is the next-greater scan O(n) despite the inner while loop?

2. For [2, 2, 3], what is the next greater element of the first 2, and which pop condition gives it?

3. In sum of subarray minimums, why is one boundary strict and the other not?

Key takeaways

• Keep a monotonic stack; pop what the current element beats; the top is the answer. O(n).
• <= versus < in the pop decides how duplicates are treated.
• Previous and next smaller give each element's span as the minimum: sum x span counts, windows and rectangles.
• Make one side strict and the other non-strict to avoid counting ties twice.