Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardmonotonic-stack

Largest Rectangle in Histogram

Problem (restated)

Bars of unit width with heights heights[i]. Return the area of the largest rectangle contained in the histogram.

Intuition

For each bar, the widest rectangle that uses it as the shortest bar spans until the first strictly shorter bar on the left and on the right. A monotonic increasing stack finds those bounds in amortized O(1) per bar.

Approaches

Increasing stack + sentinel flush

Unverified

Time O(n)Space O(n)

Idea. Stack of indices with strictly increasing heights. When a lower bar arrives (or a virtual height-0 at the end), pop and compute height * (right - left - 1) where right = i and left is the new top (or -1).

Walkthrough. [2,1,5,6,2,3] → largest is height 5 width 2 = 10 (bars at indices 2-3), overall answer 10.

Trade-offs. Two-pass “nearest smaller left/right” arrays also work at O(n) but use more memory and code. Brute force is O(n²).

Solution

export function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  const stack: number[] = []; // increasing heights by index
  let best = 0;
  for (let i = 0; i <= n; i++) {
    const h = i === n ? 0 : heights[i]!;
    while (stack.length && h < heights[stack[stack.length - 1]!]!) {
      const height = heights[stack.pop()!]!;
      const left = stack.length ? stack[stack.length - 1]! : -1;
      const width = i - left - 1;
      best = Math.max(best, height * width);
    }
    stack.push(i);
  }
  return best;
}

export function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  const stack: number[] = []; // increasing heights by index
  let best = 0;
  for (let i = 0; i <= n; i++) {
    const h = i === n ? 0 : heights[i]!;
    while (stack.length && h < heights[stack[stack.length - 1]!]!) {
      const height = heights[stack.pop()!]!;
      const left = stack.length ? stack[stack.length - 1]! : -1;
      const width = i - left - 1;
      best = Math.max(best, height * width);
    }
    stack.push(i);
  }
  return best;
}

Template connection

Monotonic stack for nearest smaller bounds (increasing stack). Contrast with next-greater (decreasing stack) in 496/503/739.

Expand per bar

Unverified

Time O(n²)Space O(1)

Idea. For each index as the shortest bar, expand left/right while bars are at least as tall; area = h * width.

Trade-offs. Easy to derive; too slow for large n. The stack version is the O(n) upgrade.

Solution

/** O(n²): for each bar expand left/right while height >= h[i]. */
export function largestRectangleAreaBrute(heights: number[]): number {
  let best = 0;
  const n = heights.length;
  for (let i = 0; i < n; i++) {
    let lo = i, hi = i;
    while (lo > 0 && heights[lo - 1]! >= heights[i]!) lo--;
    while (hi + 1 < n && heights[hi + 1]! >= heights[i]!) hi++;
    best = Math.max(best, heights[i]! * (hi - lo + 1));
  }
  return best;
}

/** O(n²): for each bar expand left/right while height >= h[i]. */
export function largestRectangleAreaBrute(heights: number[]): number {
  let best = 0;
  const n = heights.length;
  for (let i = 0; i < n; i++) {
    let lo = i, hi = i;
    while (lo > 0 && heights[lo - 1]! >= heights[i]!) lo--;
    while (hi + 1 < n && heights[hi + 1]! >= heights[i]!) hi++;
    best = Math.max(best, heights[i]! * (hi - lo + 1));
  }
  return best;
}

Deep dive

Histogram bars form a skyline. For each bar i, the largest rectangle with height[i] as the shortest bar stretches from the previous smaller bar on the left to the next smaller on the right. A monotonic increasing stack of indices finds those bounds in one pass: when you pop i, the new top is the previous smaller, and the current index is the next smaller.

Area = height[mid] * (right - left - 1). Run a sentinel 0 at the end so every bar is popped.

Reflection

The increasing stack closes when a shorter bar arrives. Is the width i - left - 1, or measured from the index on top?
Why are the sentinels at both ends required? Check one bar, and a strictly increasing row.
On equal heights, does < split the same rectangle that <= would count once?