The monotonic stack

A monotonic stack keeps its contents in sorted order by discarding anything that breaks the order. It turns a family of O(n²) scanning problems into O(n).

Next greater element

For each element, find the first later element that is larger.

function nextGreater(items) {
  const result = new Array(items.length).fill(-1);
  const stack = [];                     // holds indices, values decreasing

  for (let i = 0; i < items.length; i++) {
    // Everything smaller than items[i] has just found its answer.
    while (stack.length && items[stack.at(-1)] < items[i]) {
      result[stack.pop()] = items[i];
    }

    stack.push(i);
  }

  return result;                        // anything still stacked has no greater element
}

The nested while looks quadratic and is not: each index is pushed once and popped once, so the total work is O(n) — the standard amortised argument, and exactly what an interviewer wants to hear you say.

Store indices, not values

Indices give you both the value (items[i]) and the distance (i - stack.at(-1)), and distance is what most variants actually ask for. "Daily temperatures — how many days until it gets warmer" is this code with result[stack.pop()] = i - stack.at(-1).

Largest rectangle in a histogram

The hardest classic in this family. For each bar, the rectangle it can anchor extends until a shorter bar appears on either side — precisely what a monotonic increasing stack tracks:

function largestRectangle(heights) {
  const stack = [];             // indices with increasing heights
  let best = 0;

  for (let i = 0; i <= heights.length; i++) {
    const height = i === heights.length ? 0 : heights[i];   // sentinel drains the stack

    while (stack.length && heights[stack.at(-1)] >= height) {
      const h = heights[stack.pop()];
      const left = stack.length ? stack.at(-1) + 1 : 0;
      best = Math.max(best, h * (i - left));
    }

    stack.push(i);
  }

  return best;
}

The trailing sentinel of height 0 is the trick that avoids a separate drain loop after the main pass.

Recognising the pattern

The words are consistent: next greater, previous smaller, span, how far until, largest rectangle, trapping rain water. All of them ask about the nearest element on one side satisfying a comparison, and all of them are one pass with a monotonic stack.