Coding Interview: How Do You Find the Largest Rectangle in a Histogram?

Problem and Applicable Scenarios

Given heights, each value represents a histogram bar of width 1. A valid rectangle spans one or more consecutive bars, starts on the baseline, and cannot be taller than the shortest bar in that span. Return its maximum area.

heights = [2, 1, 5, 6, 2, 3]
answer = 10

The best rectangle covers indices 2..3: its height is 5, width is 2, and area is 10. The standard constraints are 1 <= heights.length <= 100000 and 0 <= heights[i] <= 10000. This article also defines an empty input to return 0. Under the standard limits, the area is at most 10^9, which is exactly representable by JavaScript's number type.

Current English interview-preparation material and an independent Chinese public solution both present this exact problem as a monotonic-stack exercise. The original problem and a current DSA guide use the same width-1 model and constraints. That supports treating it as a representative coding question without attributing it to a company or claiming an unverifiable frequency.

What the Interviewer Is Evaluating

The first signal is whether you can model every possible rectangle without enumerating every pair of boundaries. For any chosen height, the best rectangle extends until the first strictly shorter bar on each side. That converts a geometric-looking problem into nearest-smaller-boundary queries.

The second signal is whether you can derive the data structure. A stack of increasing heights keeps bars whose right boundary is still unknown. When a shorter bar arrives, it closes one or more of those rectangles. The current index is their first shorter position on the right; the start stored with each bar already encodes how far left it can extend.

The third signal is correctness under duplicates and boundaries. Equal heights should not create competing entries with different starts. Bars left on the stack at the end still need a right boundary. A strong implementation makes both rules explicit instead of relying on a memorized width formula.

Finally, the nested while loop needs amortized analysis. One iteration can pop many entries, but each entry is pushed once and popped once. The total number of stack operations is linear.

Clarifying Questions Before Answering

• Does every bar have width 1? Yes. Variable widths change both the stored left boundary and the area formula.
• Must the rectangle use consecutive bars? Yes. A rectangle cannot skip a short bar in the middle.
• Can heights be zero or repeated? Yes. Zero separates positive rectangles; equal heights require a consistent stack rule.
• Can the input be empty? The standard problem excludes it, while this implementation returns 0 as a documented extension.
• Do we return only the area? Yes. Returning coordinates requires retaining the winning start, end, and height plus a tie rule.
• May the function mutate the input? No mutation is necessary; the sentinel is virtual rather than appended.
• Could the area overflow? Not under the stated constraints. A larger production contract should calculate its bound and use bigint or a wider integer where required.
• Is linear time required? Yes. An O(n^2) baseline is useful for derivation and testing, but not sufficient for the target constraints.

30-Second Answer Framework

“For a bar of height h, its widest valid rectangle ends just before the first shorter bar on each side. I scan left to right with a stack of pairs (start, height) in strictly increasing height order. When the current height is lower than the stack top, the current index is that top bar's first shorter boundary on the right, so I pop it and calculate height * (right - start). I carry the popped start leftward because the current shorter bar can extend across every taller bar just removed. I keep the earlier entry when heights are equal. A virtual zero at the end closes all remaining rectangles. Each entry is pushed and popped at most once, so time and auxiliary space are O(n) and O(n).”

Step-by-Step Deep Dive

Step 1: Establish a correct baseline.

For every interval [left, right], track its minimum height. Its largest full-width rectangle has area:

min(heights[left..right]) * (right - left + 1)

Extending right while maintaining the running minimum produces an O(n^2)-time, O(1)-space oracle. It is too slow for n = 100000, but it is excellent for checking an optimized solution on small random inputs.

Step 2: Reverse the enumeration.

Instead of asking for the minimum of every interval, choose a bar as the rectangle's limiting height. If the nearest strictly shorter positions are leftShorter and rightShorter, then the bar can cover:

(leftShorter + 1) .. (rightShorter - 1)
width = rightShorter - leftShorter - 1

This is the widest rectangle for that limiting height. The global answer is the maximum over all such candidates.

Step 3: Keep unresolved bars in increasing order.

The stack stores { start, height }. Heights are strictly increasing. start is the earliest index from which that height has remained valid after all previously closed taller bars were removed. A new taller bar starts at its own index. A new shorter bar closes taller entries and inherits the earliest popped start.

For [2, 1, 5, 6, 2, 3], height 2 at index 4 first pops 6, producing 6 * 1, then pops 5, producing 5 * 2 = 10. It inherits start 2, because height 2 can cover the two taller bars. The existing height 1 remains below it and stops further extension.

Step 4: Define equality and completion.

If the current height equals the top height, keep the older entry. The two bars offer the same height, but the older one has an earlier start and therefore never yields a narrower best rectangle. A virtual height 0 at index n closes all positive entries without mutating the input or duplicating cleanup logic.

Step 5: Implement the invariant and prove the pop calculation.

interface StackBar {
  start: number
  height: number
}

export function largestRectangleArea(heights: number[]): number {
  const stack: StackBar[] = []
  let maxArea = 0

  for (let right = 0; right <= heights.length; right += 1) {
    const height = right === heights.length ? 0 : heights[right]
    let start = right

    while (stack.length > 0 && stack[stack.length - 1].height > height) {
      const bar = stack.pop()!
      maxArea = Math.max(maxArea, bar.height * (right - bar.start))
      start = bar.start
    }

    const top = stack[stack.length - 1]
    if (height > 0 && (!top || top.height < height)) {
      stack.push({ start, height })
    }
  }

  return maxArea
}

The proof follows three invariants before each scan step:

1. Stack heights are strictly increasing.
2. For each entry, every processed bar from start through right - 1 is at least its height.
3. No strictly shorter processed bar lies inside that interval; otherwise the entry would already have been popped.

When a smaller height arrives, invariants 2 and 3 show that the popped entry can extend through right - 1, while the current bar proves it cannot extend to right. Its maximal width is therefore exactly right - start, so the calculated area is complete. Passing the popped start to the current height is safe because the current height is smaller than every removed height. Skipping an equal height is safe because the retained equal entry starts no later. The sentinel closes every entry that has no shorter real bar on its right. Thus every possible limiting height has its maximal rectangle considered, and maxArea is the optimum.

Step 6: Verify edge cases and complexity.

Use fixed cases that attack different invariants:

For stronger evidence, compare the stack result with the quadratic oracle on many small random arrays. The implementation above was checked against seven fixed cases and 20,000 randomized arrays of length 0..8 with heights 0..7. This is executable evidence, not a proof replacement; the invariants explain all possible inputs.

Each positive height is pushed at most once and popped at most once, so total time is O(n). A strictly increasing input retains all n entries until the sentinel, giving O(n) worst-case auxiliary space.

High-Quality Sample Answer

“I would first establish a quadratic oracle: for each left boundary, extend the right boundary and maintain the minimum height. That checks every possible interval, but it is too slow for 100,000 bars. The repeated question is how far a chosen height can extend before a shorter bar blocks it, which points to nearest-smaller boundaries and a monotonic stack.

My stack stores the earliest valid start together with each unresolved height, and its heights are strictly increasing. At index right, I pop while the top is taller than the current bar. The current index is the popped bar's first invalid position, so its maximal area is bar.height * (right - bar.start). I pass its start to the current height because that shorter bar can cover all taller bars just removed. If the height equals the stack top, I keep the earlier entry instead of pushing a duplicate. A virtual zero at the end closes the remaining suffix.

The stack invariant guarantees every bar between an entry's start and the current position is tall enough. The shorter current bar makes the computed right boundary final. Every entry is pushed and popped at most once, giving O(n) time and O(n) worst-case space. I would test equal heights, increasing and decreasing arrays, zeros, an empty input under this extended contract, and compare random small cases with the quadratic oracle.”

Common Mistakes

Each failure has a specific cause and correction:

• Using right - start + 1 after a pop → right is already the first invalid position → Use right - start.
• Forgetting the final flush → increasing suffixes are never evaluated → Scan one virtual zero.
• Pushing every equal height → correctness becomes tied to a more delicate pop rule → Keep the earliest equal entry.
• Claiming the inner loop makes time quadratic → each entry can be popped only once → Give the amortized count.
• Appending a sentinel to heights → callers observe mutation → Compute the sentinel virtually.

Follow-up Deep Dive

Follow-up 1: How do you return the rectangle boundaries?

Whenever an area improves, save { start: bar.start, end: right - 1, height: bar.height }. Define ties before coding: prefer the leftmost rectangle, the widest rectangle, or the tallest rectangle. Area alone does not determine a unique answer.

Follow-up 2: What if bars have variable widths?

Replace index width with prefix sums of physical widths. Stack entries must retain the earliest horizontal coordinate, and a popped area becomes height * (currentX - startX). Zero-width bars and invalid negative widths need an explicit contract.

Follow-up 3: How does this extend to a binary matrix?

Treat each row as the base of a histogram. For each column, increment its height when the current cell is 1, otherwise reset it to 0; run the histogram algorithm after every row. For an m × n matrix, time is O(mn) and auxiliary space is O(n).

Follow-up 4: Can the exact answer be maintained for a stream?

The stack can process bars online, but rectangles still open at the stream's right edge are not final. A snapshot can calculate their temporary areas using the current length without popping them. Exact state can grow to O(n) on a strictly increasing stream; a fixed-memory exact algorithm does not follow from this invariant.

Follow-up 5: What if the input is too large for one machine's memory?

Independent chunk maxima are insufficient because the winning rectangle may cross chunk boundaries. A distributed summary must preserve enough boundary height structure to merge adjacent chunks, which can itself be linear in a monotone chunk. State that lower-bound risk before promising a constant-size merge summary.

Follow-up 6: When is a different approach preferable?

The quadratic oracle is best for small-input verification. Divide and conquer around the minimum is useful for deriving the recurrence, but a linear scan for each minimum becomes O(n^2) on sorted input. A range-minimum data structure can support other repeated queries, yet for this one static maximum, the monotonic stack is simpler and asymptotically optimal.