Monotonic Stack — Next Greater Element

What does it solve?

For every element in an array, find the next greater element to its right (or none). The brute-force answer scans right from each index for O(N²). A monotonic decreasing stack does it in one pass.

Key insight: keep a stack of indices whose values stay decreasing from bottom to top. When the incoming value a[i] is greater than the value on top, that top element has just found its answer: pop it and record a[i] as its next greater. Keep popping while the top is smaller, then push i. Whatever is left in the stack at the end has no greater element to its right.

The core idea

// decreasing stack of indices
res[] = -1, stack = empty
for i in 0..n-1:
  while stack && a[top] < a[i]:
    res[top] = a[i]; pop
  push i

Complexity

Time complexity

O(N)

Each index is pushed once and popped at most once. Despite the inner while loop, total pops are bounded by N, so the whole scan is linear.

Space complexity

O(N)

The stack holds at most N indices (a strictly decreasing sequence), plus the result array. No nested rescans.

Examples & edge cases

Live animation — decreasing stack resolves each next greater element

resolved (answer found) in stack (waiting) not scanned yet

i (scanning) stack top popping answer recorded

Input array

Monotonic stack (bottom → top, values decreasing)

Next greater element (-1 = none)

Current step detail

i = — stack = — pops = — resolved = —

Step — of —

—

scan pointer

stack top

—

value on top

pops

—

total so far

resolved

—

answers found

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	a[i]	Stack (vals)	Rule	Action	Result

C++ implementation

next_greater_element.cpp

#include <bits/stdc++.h>
using namespace std;

// Next Greater Element to the right via a monotonic DECREASING stack.
// The stack holds indices; their values stay decreasing bottom -> top.
vector<int> nextGreater(vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1);   // -1 = no greater element to the right
    stack<int> st;            // stores indices

    for (int i = 0; i < n; i++) {
        // pop everything smaller than a[i]: a[i] is their next greater
        while (!st.empty() && a[st.top()] < a[i]) {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);              // keep the stack decreasing
    }
    return res;                 // indices left in the stack keep -1
}

int main() {
    vector<int> a = {2,1,2,4,3};
    vector<int> r = nextGreater(a);
    for (int x : r) cout << x << " "; // 4 2 4 -1 -1
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars