Next Greater Element

For each position i, find the smallest j > i with a[j] > a[i] (or -1). Nested loops are O(n²) and die at n = 2·10⁵. The structure is a monotonic stack of indices whose values are decreasing (for *strictly greater*).

Invariant: the stack is decreasing by value. When a[i] arrives, pop while the top is smaller than a[i] — those popped indices have just found their next greater (i). Then push i.

CSES Nearest Smaller Values is the twin with a greater-to-smaller flip. USACO Gold 'Stacks' is this lesson.

Next greater to the right, -1 if nonejs

function nextGreater(a) {
  const n = a.length;
  const ans = Array(n).fill(-1);
  const st = []; // indices, values decreasing
  for (let i = 0; i < n; i++) {
    while (st.length && a[st[st.length - 1]] < a[i]) {
      ans[st.pop()] = a[i];
    }
    st.push(i);
  }
  return ans;
}

TRACE

a = [2, 1, 2, 4]. Build next greater.

i = 0, a=2

Stack empty. Push 0. ans = [-1,-1,-1,-1], st = [0].

1 / 4

CHECK

Why is the algorithm O(n) and not O(n²) in the worst case?

CHECK

You need the next greater *to the left*. What changes?

Checks 0/2

Next lesson