Largest Rectangle in Histogram

Master this topic with zero to advance depth.

Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, find the area of the largest rectangle in the histogram.

Visual Representation

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

Processing:
1. 2: Stack [2]
2. 1: 1 < 2. Pop 2. Area = 2 * (1) = 2. Push 1.
3. 5: 5 > 1. Push 5.
4. 6: 6 > 5. Push 6.
5. 2: 2 < 6. Pop 6. Area = 6 * (1) = 6. 
     2 < 5. Pop 5. Area = 5 * (2) = 10.
     Push 2.
...
Max Area: 10 (from heights 5 and 6)

Hard

Examples

Input: heights = [2,1,5,6,2,3]
Output: 10

Approach 1

Level I: Brute Force (All Pairs)

Intuition

For every possible pair of bars (i, j), the height of the rectangle is determined by the shortest bar between them. Calculate the area for all such pairs and track the maximum.

⏱ O(N^2)💾 O(1)

java

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 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]);
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }
}

Approach 2

Level III: Optimal (Monotonic Stack)

Intuition

As we iterate through the heights, we maintain a monotonic increasing stack of indices. If the current bar is shorter than the bar at the stack top, the stack top's rectangle is limited by the current bar. We pop the stack top and calculate its area: the width is the distance between the current index and the new stack top's index.

⏱ O(N)💾 O(N)

Detailed Dry Run

i	h[i]	Stack	Action	Area Calculation
0	2	`[0]`	Push	-
1	1	`[1]`	Pop 0	h[0]=2, w=1-0=1, Area=2
2	5	`[1, 2]`	Push	-
3	6	`[1, 2, 3]`	Push	-
4	2	`[1, 4]`	Pop 3, 2	h[3]=6, w=4-2-1=1, A=6; h[2]=5, w=4-1-1=2, A=10

java

import java.util.Stack;
public class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                int h = heights[stack.pop()];
                int w = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h * w);
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            int h = heights[stack.pop()];
            int w = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, h * w);
        }
        return maxArea;
    }
}

← Previous QuestionNext Greater Element II

Next Question →Maximal Rectangle

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.