Largest Rectangle in Histogram

HardArray Stack

An advertising firm wants to paint the largest possible rectangular mural across the fronts of a row of buildings. The buildings stand side by side, each exactly 1 unit wide, and building i is heights[i] units tall.

The mural has to be an axis-aligned rectangle that rests on the ground. It may stretch across several adjacent buildings, but it cannot rise above the shortest building it covers. Return the largest area such a mural can have.

Example 1

Input: heights = [2,5,4,5,1]
Output: 12

Explanation: Buildings 1 to 3 are all at least 4 tall, so a 4 × 3 mural fits.

Example 2

Input: heights = [3,3,0,3]
Output: 6

Explanation: The building of height 0 splits the row. The best mural covers the first two buildings: 3 × 2 = 6.

Example 3

Input: heights = [6,1,2]
Output: 6

Explanation: Any mural wider than one building has to cover the building of height 1, so the tallest building on its own wins with an area of 6.

Constraints

There are between 1 and 10^5 buildings.
Each building is between 0 and 10^4 units tall.

💡 Hint 1

Every optimal rectangle is as tall as some bar i. For that bar, how far can the rectangle stretch left and right?

💡 Hint 2

It stretches until the first strictly shorter bar on each side. Finding those boundaries naively is O(n²).

💡 Hint 3

Keep a stack of indices with increasing heights. When a shorter bar arrives, it is the right boundary of every taller bar you pop, and the new stack top is the left boundary.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

The best rectangle is limited by its shortest bar, so for each bar i consider the widest rectangle of height heights[i]: it extends until the nearest strictly shorter bar on each side. A monotonic stack of indices with increasing heights finds both boundaries in one pass. Scan left to right, and treat position n as an extra bar of height 0 so everything gets flushed at the end. While the current height is below the height at the stack top, pop that index top: the current index i is its right boundary, and the index now on top of the stack (or -1 if empty) is its left boundary, giving area heights[top] * (i - left - 1). Then push i. Each index is pushed and popped once.

Time O(n)Space O(n)

function largestRectangleArea(heights) {
  const n = heights.length;
  const stack = [];
  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 top = stack.pop();
      const left = stack.length ? stack[stack.length - 1] : -1;
      best = Math.max(best, heights[top] * (i - left - 1));
    }
    stack.push(i);
  }
  return best;
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length, best = 0, top = -1;
        int[] stack = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int h = i == n ? 0 : heights[i];
            while (top >= 0 && h < heights[stack[top]]) {
                int height = heights[stack[top--]];
                int left = top >= 0 ? stack[top] : -1;
                best = Math.max(best, height * (i - left - 1));
            }
            stack[++top] = i;
        }
        return best;
    }
}

/**
 * @param {number[]} heights
 * @return {number}
 */
function largestRectangleArea(heights) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit