Largest Rectangle In Histogram

The problem

The list heights describes a histogram: a row of bars standing side by side on one baseline. Each bar is 1 wide, and each number is the height of one bar. Return the area of the largest rectangle that fits inside the bars and stands on the baseline. A rectangle may cover several neighboring bars, but it can be no taller than the shortest bar it covers. A bar of height 0 is a gap that no rectangle can cross, and if every bar has height 0 the answer is 0.

What to write

function solve(heights: number[]): number

Input
heights = [2,1,5,6,2,3]

Output
10

Input
heights = [2,4]

Output
4

Constraints

1 ≤ heights.length ≤ 100000; heights are nonnegative integers.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There can be 100,000 bars. Trying every left edge with every right edge is about 5 billion rectangles, which is far too many. Aim to visit each bar once and do only a little work for it.

2. Hint 2: Ask a smaller question

   Pick one bar and say the rectangle must be exactly as tall as that bar. How far can it stretch to the left and to the right? What kind of bar stops it on each side?

3. Hint 3: Name the pattern

   For each bar you need the nearest lower bar on its left and on its right. Put each bar on a stack and leave it there until a lower bar arrives. The heights on the stack then never go down from bottom to top. A stack kept in order like this is a monotonic stack. Read the lesson on monotonic stack.

4. Hint 4: State the invariant

   The heights on the stack never decrease from bottom to top. So when a bar is popped, the bar that pops it is the first lower bar to its right, and the bar under it is the nearest bar to its left that is not taller.

5. Hint 5: Sketch the pseudocode

   Use best = 0 and an empty stack of positions. Visit each position i, then one more with height 0. While the top bar is taller than the current one, pop it; its rectangle's width is i minus the new top minus 1, or i if the stack is empty; keep the largest height times width. Push i. Return best.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Keep indices of nondecreasing bars. A shorter bar determines the right boundary of each taller bar popped from the stack.

The slow way

Try every pair of a left edge and a right edge. The rectangle between them is as tall as the shortest bar in that range, so its area is that height times the width. It is correct, but 100,000 bars give about 5 billion pairs.

The insight

The best rectangle is exactly as tall as one of its bars, the shortest one it covers. So it is enough to ask, for each bar, how wide a rectangle of that bar's height can be. It stretches both ways until it meets a lower bar, and a stack lets you measure all of these rectangles in one pass.

Step by step

1. Keep a stack of bars whose rectangle can still grow to the right. A bar's rectangle keeps growing to the right until a lower bar appears. The stack holds the positions of the bars still waiting for that, and their heights never decrease from bottom to top.
2. Visit every bar, then one extra bar of height 0. The extra bar is lower than every bar that can hold a rectangle, so it takes all of those off the stack. Without it, the bars still waiting at the end would never be measured.
3. While the bar on top is taller than this one, take it off. The current bar is the first lower bar to the right of the bar on top, so that bar's rectangle ends here. The tallest waiting bar is always on top, so taller bars come off one by one.
4. Measure its rectangle: all the bars between the new top and this one. Every bar between those two is at least as tall as the popped bar, so its height fits across all of them. With an empty stack, the rectangle reaches back to the first bar.
5. This bar now waits on the stack for a lower bar of its own. All the taller bars are gone, so the bars left on the stack are no taller than this one, and the heights still never decrease toward the top.
6. The largest area measured is the answer. Every bar taller than 0 was popped once, and the widest rectangle of each bar's height was among those measured, so the best rectangle was seen.

The same numbered steps are the comments in each solution.

function solve(heights) {
  // 1. Keep a stack of bars whose rectangle can still grow to the right
  const stack = [];
  let best = 0;
  // 2. Visit every bar, then one extra bar of height 0
  for (let i = 0; i <= heights.length; i++) {
    const h = heights[i] ?? 0;
    // 3. While the bar on top is taller than this one, take it off
    while (stack.length && heights[stack.at(-1)] > h) {
      const height = heights[stack.pop()];
      // 4. Measure its rectangle: all the bars between the new top and this one
      best = Math.max(best, height * (i - (stack.at(-1) ?? -1) - 1));
    }
    // 5. This bar now waits on the stack for a lower bar of its own
    stack.push(i);
  }
  // 6. The largest area measured is the answer
  return best;
}

function solve(heights: number[]): number {
  // 1. Keep a stack of bars whose rectangle can still grow to the right
  const stack: number[] = [];
  let best = 0;
  // 2. Visit every bar, then one extra bar of height 0
  for (let i = 0; i <= heights.length; i++) {
    const h = heights[i] ?? 0;
    // 3. While the bar on top is taller than this one, take it off
    while (stack.length && heights[stack.at(-1)!] > h) {
      const height = heights[stack.pop()!];
      // 4. Measure its rectangle: all the bars between the new top and this one
      best = Math.max(best, height * (i - (stack.at(-1) ?? -1) - 1));
    }
    // 5. This bar now waits on the stack for a lower bar of its own
    stack.push(i);
  }
  // 6. The largest area measured is the answer
  return best;
}

def solve(heights):
    # 1. Keep a stack of bars whose rectangle can still grow to the right
    stack = []
    best = 0
    # 2. Visit every bar, then one extra bar of height 0
    for i, current in enumerate(heights + [0]):
        # 3. While the bar on top is taller than this one, take it off
        while stack and heights[stack[-1]] > current:
            height = heights[stack.pop()]
            # 4. Measure its rectangle: all the bars between the new top and this one
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        # 5. This bar now waits on the stack for a lower bar of its own
        stack.append(i)
    # 6. The largest area measured is the answer
    return best

Example 1, traced

Input
heights = [2,1,5,6,2,3]

Output
10

Why it works

When a bar is popped, the bar that pops it is the first lower bar on its right, and the bar under it on the stack is the nearest bar on its left that is not taller. Everything between is at least as tall, so the measured rectangle fits. If the bar on the left is equally tall, the wider rectangle is measured later, when that bar is popped.

Time and space

Time O(n), extra space O(n). Each bar is pushed once and popped at most once, so all the popping together takes at most n steps: O(n) time, even though one loop sits inside another. When the heights keep rising, every bar waits on the stack at once: O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not forget the extra bar of height 0 at the end. Without it, the bars still on the stack are never measured: the list 2, 4 would return 0 instead of 4.
• Measure the width back to the bar under the popped one, not from the popped bar. In 3, 2, 4 the bar of height 2 spans all three bars: area 6. Counting from its own position gives only 4.
• When the stack is empty after a pop, the rectangle reaches back to the first bar. Use -1 as the position under the popped bar. With 0, the list 1, 1 gives 1 instead of 2.

Pattern

Monotonic stack. Builds on Daily Temperatures.

Keep going