Stacks & QueuesProblem 17 of 38
Largest rectangular Area in Histogram
Problem Statement
Given an array of integers representing the heights of bars in a histogram where each bar has width 1, find the area of the largest rectangle that can be formed within the histogram.
Example:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle has area 10 units (formed by heights[2]=5 and heights[3]=6)
█
█ █
█ █ █
█ █ █ █ █
█ █ █ █ █ █
2 1 5 6 2 3
Input: heights = [2,4]
Output: 4
Approach 1: Brute Force
Intuition
For each bar, find the maximum rectangle with that bar as the smallest bar. Expand left and right until we find a shorter bar.
Algorithm
- For each bar at index i
- Expand left while heights[left] >= heights[i]
- Expand right while heights[right] >= heights[i]
- Calculate area = heights[i] * (right - left + 1)
- Track maximum area
java
public class LargestRectangleHistogram {
public static int largestRectangleBruteForce(int[] heights) {
int n = heights.length;
int maxArea = 0;
for (int i = 0; i < n; i++) {
int minHeight = heights[i];
for (int j = i; j < n; j++) {
minHeight = Math.min(minHeight, heights[j]);
int width = j - i + 1;
int area = minHeight * width;
maxArea = Math.max(maxArea, area);
}
}
return maxArea;
}
}Complexity Analysis
- Time Complexity: O(n^2) - nested loops
- Space Complexity: O(1)
Approach 2: Using Stack (Optimal)
Intuition
Use a stack to find the Previous Smaller Element (PSE) and Next Smaller Element (NSE) for each bar. The width of the largest rectangle with bar i as the shortest is (NSE[i] - PSE[i] - 1).
Algorithm
- For each bar, find the index of the nearest smaller bar on the left (PSE)
- Find the index of the nearest smaller bar on the right (NSE)
- Width = NSE[i] - PSE[i] - 1
- Area = heights[i] * width
- Use stack to compute PSE and NSE in O(n)
java
import java.util.*;
public class LargestRectangleHistogram {
public static int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] leftSmaller = new int[n];
int[] rightSmaller = new int[n];
Stack<Integer> stack = new Stack<>();
// Find Previous Smaller Element indices
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
leftSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
// Clear stack
stack.clear();
// Find Next Smaller Element indices
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
rightSmaller[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
// Calculate maximum area
int maxArea = 0;
for (int i = 0; i < n; i++) {
int width = rightSmaller[i] - leftSmaller[i] - 1;
int area = heights[i] * width;
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
// Single pass solution
public static int largestRectangleAreaOnePass(int[] heights) {
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
int n = heights.length;
for (int i = 0; i <= n; i++) {
int currentHeight = (i == n) ? 0 : heights[i];
while (!stack.isEmpty() && currentHeight < 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));
System.out.println("One Pass: " + largestRectangleAreaOnePass(heights));
}
}Complexity Analysis
- Time Complexity: O(n) - each element is pushed and popped once
- Space Complexity: O(n) - for stack and auxiliary arrays
Key Takeaways
- Key insight: For each bar, find how far left and right it can extend
- Stack maintains increasing heights - when a smaller height comes, pop and calculate area
- Single pass optimization: Process popped elements immediately when a smaller element arrives
- The width for a popped bar is: current_index - stack_top_after_pop - 1
- Use -1 and n as virtual boundaries when stack is empty
- This is a classic monotonic stack problem - master this for many similar problems