Largest Rectangle in a Histogram

Given an int[] of the heights of the bars in a histogram, where every bar has width 1, return the area of the largest rectangle that fits inside it.

LeetCode: 84. Largest Rectangle in Histogram

Example

Input:  [2, 1, 5, 6, 2, 3]
Output: 10   (bars 5 and 6: width 2, height 5)

Brute force: every start, extend right

For each starting bar i, extend the rectangle to the right one bar at a time. Its height is the minimum bar seen so far.

public class Main {
    static long largestRectangle(int[] heights) {
        long best = 0;
        for (int i = 0; i < heights.length; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                best = Math.max(best, (long) minHeight * (j - i + 1));
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(largestRectangle(new int[]{2, 1, 5, 6, 2, 3}) + " " + largestRectangle(new int[]{2, 4}));
    }
}

10 4

Time: O(n²). Space: O(1).

Optimal: a monotonic stack

The largest rectangle is as tall as one of the bars: its shortest bar. For each bar k, the widest rectangle of height heights[k] extends left and right until the first shorter bar on each side.

A stack of indices (an ArrayDeque<Integer>, with push, pop, and peek at the top) with increasing heights finds both boundaries. When bar i is shorter than the bar on top, that top bar k has found its right boundary (i). Its left boundary is the bar below it in the stack, because everything between them was popped for being taller. Pop k and compute its rectangle:

width = i - left - 1      (left = the index below k, or -1 if the stack is empty)
area  = heights[k] * width

A final pass with i = n (height 0) flushes the bars still on the stack.

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static long largestRectangle(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>(); // indices, heights increasing
        long best = 0;
        for (int i = 0; i <= n; i++) {
            int h = i < n ? heights[i] : 0;
            while (!stack.isEmpty() && heights[stack.peek()] >= h) {
                int k = stack.pop();
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                best = Math.max(best, (long) heights[k] * width);
            }
            stack.push(i);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(largestRectangle(new int[]{2, 1, 5, 6, 2, 3}) + " " + largestRectangle(new int[]{2, 4}));
        System.out.println(largestRectangle(new int[]{3, 3, 3}) + " " + largestRectangle(new int[]{}));
    }
}

10 4
9 0

Time: O(n): each index is pushed and popped at most once. Space: O(n).

Popping on equal heights (heights[stack.peek()] >= h in the loop above) is fine: the earlier equal bar gets a rectangle that's too narrow, but the later one extends over it and gets the full width.

Edge cases

• Empty histogram: 0.
• Increasing heights: nothing is popped until the end.
• Overflow: the area can exceed the int range (for example 100,000 bars of height 100,000 give 10,000,000,000, and Integer.MAX_VALUE is 2,147,483,647). The product is computed as (long) height * width. Without the cast, int multiplication wraps silently.

The same stack solves Maximal Rectangle in a 0/1 matrix: treat each row as the base of a histogram of consecutive 1s above it.