Monotonic stack: next greater

For every element, find the first larger value to its right, in a single pass.

Time O(n)Space O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

The stack holds indices whose answer is still unknown, with values decreasing from bottom to top. When a bigger value arrives, it is the answer for everything smaller on top of the stack.

Code

C++PythonC#

vector<int> nextGreater(const vector<int>& a) {
    vector<int> result(a.size(), -1);
    stack<int> st; // indices still waiting for an answer
    for (int i = 0; i < (int)a.size(); i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            result[st.top()] = a[i]; st.pop();
        }
        st.push(i);
    }
    return result;
}

def next_greater(a: list[int]) -> list[int]:
    result = [-1] * len(a)
    stack = []  # indices still waiting for an answer
    for i, x in enumerate(a):
        while stack and a[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

public static int[] NextGreater(int[] a) {
    var result = new int[a.Length];
    Array.Fill(result, -1);
    var stack = new Stack<int>(); // indices still waiting for an answer
    for (int i = 0; i < a.Length; i++) {
        while (stack.Count > 0 && a[stack.Peek()] < a[i])
            result[stack.Pop()] = a[i];
        stack.Push(i);
    }
    return result;
}

Tips

Each index is pushed once and popped at most once, so the nested loop is still O(n) overall.
Same pattern: daily temperatures, stock span, largest rectangle in a histogram.

In the .NET library

Array.Fill(result, -1) sets every element in one call. Store indices in the Stack<int>, not values, so you know where to write the answer.