Typorithm · hard

Largest Rectangle in Histogram

largest-rectangle-in-histogrammonotonic-stackincreasing-stackspanssentinel

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Largest Rectangle in Histogram

Monotonic Stack

An increasing stack of indices; a shorter bar pops taller ones, each forming a rectangle as wide as its span.

Each bar's largest rectangle extends left and right until a shorter bar stops it.

An increasing-height stack of indices lets a new shorter bar finalize all taller bars behind it.

The width of a popped bar's rectangle spans from just after the new stack top to the current index.

Stack holds increasing-height indices.

A shorter bar resolves taller ones.

Sentinel 0 flushes the stack at the end.

function largestRectangleArea(heights) {
  const stack = [];
  let best = 0;

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

  return best;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Flush sentinel

A virtual 0-height bar at the end pops everything left on the stack.

const h = i === heights.length ? 0 : heights[i]

2. Resolve taller bars

A lower bar finalizes every taller bar still pending.

while (stack.length > 0 && heights[stack[stack.length - 1]] >= h) {

3. Span width

Width spans from just after the new top to the current index.

const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1

4. Best rectangle

Each popped bar defines a candidate rectangle.

best = Math.max(best, height * width)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.