Largest rectangular Area in Histogram

The problem, simply

You get a row of bars standing side by side. Every bar is 1 wide, and heights[i] says how tall bar i is. Draw one rectangle that sits on the floor and stays inside the bars. Give back the largest area such a rectangle can have.

A rectangle that covers several bars can only be as tall as the shortest bar it covers.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every stretch of bars. Start at bar i, then walk right with j. Keep the shortest height seen between i and j. The rectangle over that stretch has area shortest * (j - i + 1).

1. For each start i, set low = heights[i].
2. For each end j from i to the last bar, update low = min(low, heights[j]).
3. Area is low * (j - i + 1). Keep the biggest.

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int best = 0;
        for (int i = 0; i < n; i++) {
            int low = heights[i];
            for (int j = i; j < n; j++) {
                low = Math.min(low, heights[j]);          // the banner can only be this tall
                best = Math.max(best, low * (j - i + 1));
            }
        }
        return best;
    }
}

How long it takes: about n * n / 2 stretches, O(n^2). Extra room: a few numbers, O(1). Too slow when there are 100,000 bars.

Way 2: the clever way

Each bar wants to know two things: the nearest shorter bar on its left and the nearest shorter bar on its right. Its banner fills the space between them.

Keep a stack of bar positions whose heights go up from bottom to top. Walk left to right.

1. Look at bar i with height h. While the bar on top of the stack is taller than h, that top bar has found its right wall: bar i. Pop it.
2. Its left wall is the bar now on top of the stack (the stack is sorted, so that bar is shorter). If the stack is empty, it can reach all the way to the start.
3. Width is i - left - 1, or i if the stack is empty. Area is height * width. Keep the biggest.
4. Push i.
5. At the end, pretend there is one more bar of height 0. It pops everything that is left.

import java.util.*;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>();   // bar positions, heights going up
        int best = 0;
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];       // a pretend bar of height 0 at the end
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int tall = heights[stack.pop()];     // this bar just found its right wall
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                best = Math.max(best, tall * width);
            }
            stack.push(i);
        }
        return best;
    }
}

How long it takes: every bar is pushed once and popped once, so the whole walk is O(n). Extra room: the stack can hold every bar when the heights only go up, O(n).

Watch out for

• Forgetting the pretend 0 bar at the end. Bars still on the stack never get measured, and stairs going up return the wrong answer.
• Using <= instead of < when popping. Both give the right answer for equal heights, because the last equal bar still measures the full width. Pick one and be ready to explain why.
• Area can overflow int if heights and n are both huge. Use long for best if the limits allow it.

What interviewers ask next

• Maximal rectangle of 1s in a 0 and 1 grid. Go row by row and treat each column as a bar whose height is the number of 1s stacked above. Run this histogram trick on every row. O(rows * cols).
• Can you do it with two passes instead? Yes. One pass finds the nearest shorter bar on the left for every bar, another finds it on the right, then area = h * (right - left - 1). Same O(n).
• Trapping rain water looks similar. It uses the tallest bar on each side instead of the nearest shorter one, and can be done with two pointers and O(1) room.
• Sum of the minimum of every subarray. The same "how far can this bar stretch while it is the smallest" idea counts how many subarrays have each bar as their minimum.

Remember this

Grown-up words: the towers are a histogram, the pile of rising bars is a monotonic increasing stack, the walls are the previous smaller element and the next smaller element, and the pretend 0 bar is a sentinel.