Next Greater Element

Problem. For each element of an array, find the first element to its right that is strictly greater (or $-1$ if none).

Monotonic stack — $O(n)$

vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1);
    stack<int> st;                                   // indices, decreasing values
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            res[st.top()] = a[i];                    // i is the answer for st.top()
            st.pop();
        }
        st.push(i);
    }
    return res;
}

Each index is pushed once and popped once, so the total is $O(n)$ despite the inner while. The stack holds exactly the indices still waiting for an answer — those whose value has not yet been exceeded.

The four directions

Want	Direction	Pop while
Next greater	left to right	a[st.top()] < a[i]
Next smaller	left to right	a[st.top()] > a[i]
Previous greater	left to right, read the top before pushing	a[st.top()] <= a[i]
Previous smaller	left to right, read the top before pushing	a[st.top()] >= a[i]

For “previous”, read st.top() before pushing $i$; for “next”, assign the answer while popping.

Strict vs non-strict (< vs <=) decides how ties are handled — and it matters. When counting “subarrays where this element is the minimum”, use strict on one side and non-strict on the other so that equal elements are attributed to exactly one of them.

Circular version

Traverse the array twice, using indices mod $n$:

for (int i = 0; i < 2 * n; i++) {
    while (!st.empty() && a[st.top()] < a[i % n]) { res[st.top()] = a[i % n]; st.pop(); }
    if (i < n) st.push(i);                           // only push during the first pass
}

Pushing only in the first pass prevents duplicate entries.

What it unlocks

Problem	Uses
Largest rectangle in a histogram	previous and next smaller
Maximal rectangle in a binary matrix	the above, per row
Trapping rain water	next greater on both sides
Sum of subarray minimums	count where each element is the minimum
Sum of subarray ranges	max-sum minus min-sum
Stock span	previous greater
Daily temperatures	next greater (distance)
Remove $k$ digits for the smallest number	greedy with a stack
Build a Cartesian tree in $O(n)$	the stack is the right spine
Count visible bars from the left	previous greater
Convex hull (monotone chain)	the same “pop while the turn is wrong” discipline

Counting subarrays where each element dominates

// for each i: subarrays in which a[i] is the minimum
long long total = 0;
for (int i = 0; i < n; i++)
    total += (long long)a[i] * (i - prevSmaller[i]) * (nextSmaller[i] - i);

This contribution technique converts an $O(n^2)$ enumeration over subarrays into $O(n)$ over elements, and it generalises to sums of maxima, of ranges, and of gcds.

The Cartesian tree connection

Building a Cartesian tree (heap by value, BST by index) with a monotonic stack is $O(n)$:

vector<int> par(n, -1), st;
for (int i = 0; i < n; i++) {
    int last = -1;
    while (!st.empty() && a[st.back()] > a[i]) { last = st.back(); st.pop_back(); }
    if (!st.empty()) par[i] = st.back();
    if (last != -1) par[last] = i;
    st.push_back(i);
}

The stack is the right spine of the tree being built. This gives the RMQ ↔ LCA reduction in linear time, and explains why the monotonic stack and the Cartesian tree keep appearing in the same problems.

Why it is worth knowing

The monotonic stack is the answer to an entire class of “for each element, find the nearest element satisfying X” questions, and the amortized argument (“each element is pushed and popped once”) is the cleanest example of aggregate analysis.

See also: Monotonic Stack · Largest Rectangle · Range Minimum Query