Monotonic stacks: let the future resolve the past

For every number, find the first strictly greater number to its right. If there is none, return -1.

For [2, 1, 2, 4, 3], the answer is [4, 2, 4, -1, -1]. A direct solution starts a new search at every index. It is easy to write—and can inspect quadratically many pairs.

A monotonic stack asks a different question: which earlier positions are still waiting for an answer? Keep just those positions. When a new value arrives, it settles every waiting position it exceeds.

A stack of unfinished questions

Scan from left to right. The stack holds indices, not merely values: an index tells us both the pending value and where to write its answer.

The stack’s values are non-increasing from bottom to top. So its top is the most recent unresolved value, and the first one a new value could possibly resolve. If the current value is larger, it is the first greater value for that top index. Pop, record the answer, and try again: one large value can settle several older questions.

The player makes the invariant visible:

• every index in the stack is still waiting for its first greater value
• their values are non-increasing from bottom to top
• every popped index has just found its answer, because nothing between it and the current value was greater

The last claim is the reason this is not a shortcut that loses information. An index stays in the stack until the first value that exceeds it arrives. The moment it is popped is exactly the moment its answer becomes known.

Equal is not greater

The two 2s are deliberately kept together. The problem asks for a value that is strictly greater, so the pop condition is current > top, not current >= top.

That single character states the contract. With >, equal values remain pending and may receive the same later answer. In a different problem—say, next greater or equal—the condition changes, and so does the invariant you must be able to say out loud.

function nextGreater(values: number[]): number[] {
  const answer = Array<number>(values.length).fill(-1);
  const pending: number[] = [];

  for (let index = 0; index < values.length; index += 1) {
    while (pending.length > 0 && values[index] > values[pending[pending.length - 1]]) {
      const earlier = pending.pop()!;
      answer[earlier] = values[index];
    }

    pending.push(index);
  }

  return answer;
}

The while is doing precisely what the animation shows: resolve every older, smaller pending value before letting the current index wait for a later one. Values still in pending keep their initialized answer, -1.

The nested loop is still linear

There is a while inside a for, but the while does not restart its work for each index. Every index enters pending once. Every index leaves it at most once.

For n input values, there are at most n pushes and n pops: at most 2n stack operations. The running time is O(n); the stack takes O(n) space in the worst case, such as a descending array.

The same promise, a different answer

Daily Temperatures asks how many days until a warmer one, rather than which warmer temperature appears. The waiting positions and pop condition do not change. Only the answer written on pop changes from a value to an index difference.

function daysUntilWarmer(temperatures: number[]): number[] {
  const days = Array<number>(temperatures.length).fill(0);
  const pending: number[] = [];

  for (let day = 0; day < temperatures.length; day += 1) {
    while (
      pending.length > 0 &&
      temperatures[day] > temperatures[pending[pending.length - 1]]
    ) {
      const earlier = pending.pop()!;
      days[earlier] = day - earlier;
    }

    pending.push(day);
  }

  return days;
}

The largest-rectangle-in-a-histogram problem uses the same delayed resolution in another costume. A bar waits on the stack while later bars are at least as tall. A shorter bar ends that promise: it is the first boundary to the right, so each popped bar now knows how far its rectangle may extend. The comparison, what the index represents, and the final calculation change; the pattern does not.

Recognize the pattern

Reach for a monotonic stack when a problem contains all three of these ideas:

• each position waits for a nearest later or earlier position with a greater or smaller value
• a new value can resolve several unresolved positions at once
• once a position is resolved, it will never need to be considered again

Then decide the contract before writing code: direction of scan, increasing or decreasing stack, strict or non-strict comparison, and whether a pop writes a value, a distance, or a boundary. The stack is not the idea. It is the compact record of questions that only the future can answer.