Java - Largest Rectangle in Histogram
Problem Statement
Given an array heights[] representing the heights of bars in a histogram, find the largest rectangular area that can be formed using these bars.
Example
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation:
- The largest rectangle can be formed using bars [5, 6], giving an area of 5 × 2 = 10.
Approach
Using Stack (Efficient Approach - O(N)):
Use a stack to keep track of bar indices.
Process each bar to determine the maximum area possible.
If the current bar is shorter than the stack’s top bar, compute the area for that height.
Brute Force (O(N²)) - Less Efficient:
Iterate over all possible rectangles.
Compute the width and height for each.
Java Code - Stack Approach (O(N))
import java.util.Stack;
public class LargestRectangle {
public static int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
int n = heights.length;
for (int i = 0; i <= n; i++) {
while (!stack.isEmpty() && (i == n || heights[i] < heights[stack.peek()])) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
public static void main(String[] args) {
int[] heights = {2, 1, 5, 6, 2, 3};
System.out.println("Largest Rectangle Area: " + largestRectangleArea(heights));
}
}
Time Complexity
O(N) (Each bar is pushed and popped once)
Java Code - Brute Force (O(N²))
public class LargestRectangle {
public static int largestRectangleArea(int[] heights) {
int maxArea = 0;
int n = heights.length;
for (int i = 0; i < n; i++) {
int minHeight = heights[i];
for (int j = i; j < n; j++) {
minHeight = Math.min(minHeight, heights[j]);
maxArea = Math.max(maxArea, minHeight * (j - i + 1));
}
}
return maxArea;
}
public static void main(String[] args) {
int[] heights = {2, 1, 5, 6, 2, 3};
System.out.println("Largest Rectangle Area: " + largestRectangleArea(heights));
}
}
Example Walkthrough
Input
heights = {2, 1, 5, 6, 2, 3}
Output
Largest Rectangle Area: 10
