Next Greater Element

For each number in a list, find the first number to its right that is bigger. If there is none, say so.

[2, 1, 2, 4, 3]
// →  4, 2, 4, ·, ·

Check the second one by hand: after the 1 comes a 2, which is bigger, so the answer is 2. The 4 has only a 3 after it, so nothing.

The obvious way

For each element, walk right until you find something bigger:

for (let i = 0; i < values.length; i++) {
  answer[i] = -1;
  for (let j = i + 1; j < values.length; j++) {
    if (values[j] > values[i]) { answer[i] = values[j]; break; }
  }
}

Correct, and $O(n^2)$. On a descending array — [5, 4, 3, 2, 1] — every inner loop runs to the end and finds nothing, which is the worst case and also a very ordinary input.

The realisation

The slow version restarts the rightward walk for every element, and those walks cover the same ground over and over.

Turn it around. Instead of each element hunting for its answer, walk left to right once and let each new value answer whoever was waiting for it.

Keep a pile of indices still waiting. When a new value arrives, it is the answer for everyone on the pile smaller than itself — so pop them, record it, and then the new value joins the pile.

Why the stack is always decreasing

Suppose the stack held two values with a smaller one below a bigger one. How would that have happened?

The smaller one was pushed first. Then the bigger one arrived — and the pushing rule pops everything smaller before pushing. So the smaller one would have been removed at that moment. The arrangement cannot exist.

The code

function nextGreater(values: readonly number[]): number[] {
  const answer = new Array<number>(values.length).fill(-1);
  const waiting: number[] = [];       // indices, decreasing by value

  for (let i = 0; i < values.length; i += 1) {
    // Everything on the stack smaller than values[i] has just found its answer.
    while (waiting.length > 0 && values[waiting[waiting.length - 1]!]! < values[i]!) {
      answer[waiting.pop()!] = values[i]!;
    }
    waiting.push(i);
  }

  // Whatever is still waiting has nothing bigger to its right; it keeps -1.
  return answer;
}

Two details worth calling out.

Store indices, not values. You need to know where to write the answer, and values[index] recovers the value anyway.

The leftovers are the answer too. Anything still on the stack at the end has no greater element, and because the array was pre-filled with -1, no cleanup loop is needed.

Linear, despite the inner loop

The while inside a for looks quadratic. It is not, and the reason is worth internalising because it recurs.

Each index is pushed exactly once and popped at most once. So across the entire run there are at most $n$ pushes and $n$ pops — no matter how they are distributed. One iteration might pop five things, but only because four earlier iterations popped none.

$O(n)$ time, $O(n)$ space. This is the same accounting that makes the sliding window linear: work inside a loop is fine as long as it is bounded in total.

The variations

The pattern generalises by changing one comparison or one direction:

That last one deserves a note: the second pass exists only to answer elements still waiting after the first, so pushing during it would let those wait twice.

Where it shows up in disguise

Daily temperatures — “how many days until it gets warmer” is this problem with i - j instead of the value.

Largest rectangle in a histogram — for each bar, the rectangle it can anchor extends until a shorter bar on each side. That is next-smaller in both directions, and the whole problem is two monotonic stack passes.

Trapping rain water — water sits between a left and right boundary, which is the same next-greater relation read as walls.

Stock span — “how many consecutive earlier days had a lower price” is previous-greater.