Largest Rectangle in Histogram

NeetCode: Largest Rectangle in Histogram · LeetCode: 84. Largest Rectangle in Histogram · Difficulty: Hard

Given bar heights of a histogram (each bar has width 1), return the area of the largest rectangle.

Example

Text

Input:  heights = [7, 1, 7, 2, 2, 4]    Output: 8    (the bars 2, 2, 4 at height 2 give 2 x 4)

Brute force: expand from every bar

The best rectangle that uses bar i as its shortest bar extends left and right as long as the neighbours are at least as tall. Compute that for every i. The area is height * width in int arithmetic. If a height times a width could exceed the int range, the product wraps silently to a wrong value, and the computation would need long.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.largestRectangleArea(new int[]{7, 1, 7, 2, 2, 4}));
        System.out.println(s.largestRectangleArea(new int[]{1, 3, 7}));
    }
}

Output

8
7

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

Optimal: monotonic stack

Keep a stack of {start index, height} pairs, stored as two-element int[] arrays in an ArrayDeque, with strictly increasing heights. A new bar shorter than the top means the top bar cannot extend any further to the right: pop it, compute its rectangle (height * (i - start)), and remember that the new bar can extend left to that popped bar's start. After the scan, everything left on the stack extends to the end. Iterating an ArrayDeque with a for-each loop visits entries from the top of the stack to the bottom; the order does not matter here because only the maximum is kept.

Java

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

class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<int[]> stack = new ArrayDeque<>(); // each entry is {start, height}
        int best = 0;
        for (int i = 0; i < heights.length; i++) {
            int h = heights[i];
            int start = i;
            while (!stack.isEmpty() && stack.peek()[1] >= h) {
                int[] top = stack.pop();
                best = Math.max(best, top[1] * (i - top[0]));
                start = top[0];
            }
            stack.push(new int[]{start, h});
        }
        int n = heights.length;
        for (int[] entry : stack) {
            best = Math.max(best, entry[1] * (n - entry[0]));
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.largestRectangleArea(new int[]{7, 1, 7, 2, 2, 4}));
        System.out.println(s.largestRectangleArea(new int[]{1, 3, 7}));
    }
}

Output

8
7

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