Monotonic Stack: Resolve Waiting Candidates in JavaScript

Recognize the Pattern

A value needs its nearest greater or smaller neighbor, or a boundary that limits its span.
The next item can permanently settle older candidates, which never need to be pushed again.
A stack resolves candidates from one end. Sliding-window expiration from the other end instead requires a deque.

Core Invariant

Stack indices have strictly increasing heights. A pop assigns the removed bar a span bounded by the new stack top and the current index.

Important Boundary

Strict versus non-strict popping depends on the task. Equal temperatures are not warmer; equal histogram heights can share a carefully assigned span.

Histogram heights 2, 1, 5, 6, 2, 3 with the width-two height-five rectangle highlighted. — At index 4, height 2 resolves heights 6 and 5. The best rectangle spans indices 2 and 3: 5 times 2 equals 10.

Name what the stack is waiting for

Keep indices, not only values, when the answer needs distance, width, or expiration. Equal temperatures are not warmer. Histogram equal heights can be handled with different consistent ownership rules; choose a comparison and derive the width for that rule.

Task	Stack meaning	Pop proves
Next warmer day	Unresolved indices with nonincreasing temperatures.	The current day is the first strictly warmer day for the popped index.
Histogram area	Indices with strictly increasing heights in this template.	The current position ends the popped bar's assigned span.
Window maximum	Deque of unexpired decreasing-value candidates.	A newer at-least-as-large value dominates an older value until expiration.

Finalize rectangle widths on pop

Template Assumptions

Finite nonnegative numeric heights; empty input returns zero.
Uses a virtual final zero and never appends to or mutates the input array.

JavaScript Template

function largestRectangleArea(heights) {
  const stack = [];
  let best = 0;
  for (let right = 0; right <= heights.length; right++) {
    const current = right === heights.length ? 0 : heights[right];
    while (stack.length && heights[stack[stack.length - 1]] >= current) {
      const index = stack.pop();
      const left = stack.length ? stack[stack.length - 1] : -1;
      best = Math.max(best, heights[index] * (right - left - 1));
    }
    if (right < heights.length) stack.push(right);
  }
  return best;
}

Keep heights strictly increasing by popping greater-or-equal heights before pushing the current index.
After popping, the new top is the left excluded boundary. The current index is the right excluded boundary, so width is right - left - 1.
A virtual zero at the end flushes remaining bars without mutating the input. With equal heights, a later equal bar inherits the farther-left span; earlier equal bars get narrower spans.

Resolve [2,1,5,6,2,3]

Incoming index: height	Popped	Important area	Stack after push
0: 2	none	0	[0]
1: 1	0	2 x 1 = 2	[1]
2: 5	none	best stays 2	[1,2]
3: 6	none	best stays 2	[1,2,3]
4: 2	3, then 2	6 x 1 = 6; 5 x 2 = 10	[1,4]
5: 3	none	best stays 10	[1,4,5]
6: virtual 0	5,4,1	3 x 1; 2 x 4; 1 x 6	[]

Step-by-Step: Histogram: resolve a rectangle when its bar is popped

Step 1 / 7

Stack indices: [0]
Stack heights: [2]
Best rectangle area: 0

Push height 2

Index 0 has no earlier bar to compare with. Push 0; its right boundary is not known yet.

Reuse the 1-D proof for Maximal Rectangle

For each matrix row, maintain consecutive-one heights per column. A zero resets its column to zero; a one increments its height. Every all-one rectangle has a bottom row, so solving the histogram at each possible bottom row covers all candidates.

Do not append a sentinel to a reused heights array without removing it. The virtual sentinel avoids growing the array across rows.
For R rows and C columns, the histogram reduction costs O(RC) time and O(C) auxiliary space.

Amortized linear work, not quadratic popping

Each index is pushed once and popped at most once: O(N) time and O(N) auxiliary space for one histogram.
Worst-case stack length is N on increasing heights. The inner while loop can pop many items once, not many times per item.
A deque for sliding maxima uses the same domination idea plus expiration. It is not interchangeable with this histogram stack.

Mistakes and Counterexamples

Treat equal values as greater without checking the task.

Counterexample: For temperatures [70,70], the second day is not warmer; answering one day for the first is incorrect.

Correction: Choose strictness from the output contract, rather than copying a histogram comparison into next-greater code.

Leave unresolved increasing bars on the stack.

Counterexample: For histogram [1,2,3], no real smaller bar arrives, yet the rectangle using the final two bars has area 4.

Correction: Flush at the end with a virtual minimum or an explicit drain loop using the array length as the right boundary.

Last-Minute Recap

State what remains unresolved.
A pop must settle a boundary or prove domination.
Derive widths using excluded boundaries and consistent equality rules.
Push once, pop once explains amortized O(N).

Explain It in an Interview

What is each stack index waiting for?
Why is rectangle width right - left - 1 after popping?
Why is the nested popping loop linear over the whole input?

Ready to Apply This Pattern?

Before coding, explain why this pattern fits and what must stay true at each step. Start with an easier problem, then test that reasoning on a harder variation.

Ordered from Easy to Hard. Premium access requirements still apply.

Difficulty4 problems