Monotonic stacks: next greater element in O(n), not O(n squared)

For every element, find the first larger value to its right. The obvious solution is two nested loops. A monotonic stack does it in one pass, at the cost of accepting that the stack holds the indices that do not have an answer yet.

The template

Scan left to right, keeping the stack in decreasing order. When a new element arrives, pop everything smaller, and those popped elements just received their answer:

function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];
  for (let i = 0; i < nums.length; i += 1) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

The crucial part is that elements popped inside the while get their answer immediately and are never discussed again. So although the inner while looks like a nested loop, its total iterations are O(n).

Why it is O(n)

The amortised argument is simple: each index is pushed once by the for loop and popped at most once. Total operations are at most 2n, independent of the data. That is the only reason it beats scanning forward from each element, whose worst case, a decreasing array, rescans to the end every time.

Four problems with the same shape

Problem	Stack order	Pop when
Next greater element	decreasing	the new value is larger
Largest rectangle in a histogram	increasing	the new bar is shorter
Trapping rain water	decreasing heights	the new bar is taller
Daily temperatures	decreasing indices	the new temperature is higher

Recognise the first larger or smaller neighbour, and the template fits. Trapping rain water is the variation that computes a pocket of water while popping.

Two details that are easy to get wrong

• Store indices, not values. Any question about distance or position, such as how many days until a warmer one, cannot be answered from the value alone. Indices are always safe.
• Decide what equals does. < versus <= decides whether duplicates get the strictly greater neighbour or the greater-or-equal one. That changes which position wins, so pick the semantics before writing the loop.

When a problem asks for the first larger or smaller thing to the left or right, reach for a stack before reaching for nested loops.