Problem Statement
Given an array heights[] representing the height of histogram bars, find the area of the largest rectangle that can be formed.
Each bar has:
Width = 1
Brute Force Intuition
In an interview, you can explain it like this:
Consider every bar as the smallest bar in a rectangle. Expand towards both left and right until a smaller bar is encountered, then compute the area.
Although straightforward, every expansion scans multiple bars repeatedly.
Complexity
- Time Complexity: O(N²)
- Space Complexity: O(1)
Brute Force Code
class Solution {
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
for (int i = 0; i < heights.length; i++) {
int minHeight = heights[i];
for (int j = i; j < heights.length; j++) {
minHeight = Math.min(minHeight, heights[j]);
int area = minHeight * (j - i + 1);
maxArea = Math.max(maxArea, area);
}
}
return maxArea;
}
}
Moving Towards the Optimal Approach
Instead of expanding for every bar:
Ask:
For every bar,
How far can it expand
towards Left and Right
before finding a smaller bar?
If we know:
- Previous Smaller Element
- Next Smaller Element
then we immediately know the rectangle width.
Pattern Recognition
Whenever you see:
- Nearest Smaller
- Largest Rectangle
- Expansion until Smaller Element
Think:
Monotonic Stack
Key Observation
For every bar:
Area
=
Height
×
Width
Width becomes:
Next Smaller Index
-
Previous Smaller Index
-
1
So we only need to compute:
Previous Smaller
Next Smaller
using Monotonic Stack.
Optimal Approach
Step 1
Find:
Previous Smaller Index
for every element.
Step 2
Find:
Next Smaller Index
for every element.
Step 3
For every index:
width = right[i] - left[i] - 1;
area = heights[i] * width;
Take maximum.
Optimal Java Solution
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = previousSmaller(heights);
int[] right = nextSmaller(heights);
int maxArea = 0;
for (int i = 0; i < n; i++) {
int width = right[i] - left[i] - 1;
int area = heights[i] * width;
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
private int[] previousSmaller(int[] arr) {
int n = arr.length;
int[] ans = new int[n];
Stack<Integer> st = new Stack<>();
for (int i = 0; i < n; i++) {
while (!st.isEmpty() &&
arr[st.peek()] >= arr[i]) {
st.pop();
}
ans[i] = st.isEmpty()
? -1
: st.peek();
st.push(i);
}
return ans;
}
private int[] nextSmaller(int[] arr) {
int n = arr.length;
int[] ans = new int[n];
Stack<Integer> st = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() &&
arr[st.peek()] >= arr[i]) {
st.pop();
}
ans[i] = st.isEmpty()
? n
: st.peek();
st.push(i);
}
return ans;
}
}
Dry Run
Input
heights = [2,1,5,6,2,3]
Previous Smaller
Index
0 → -1
1 → -1
2 → 1
3 → 2
4 → 1
5 → 4
Next Smaller
Index
0 → 1
1 → 6
2 → 4
3 → 4
4 → 6
5 → 6
Area Calculation
For:
Height = 5
Width:
4 - 1 - 1
= 2
Area:
5 × 2 = 10
Largest Area:
10
Why Monotonic Stack Works?
Each bar is:
Pushed once
Popped once
Hence every index is processed only once.
The stack efficiently finds:
Nearest Smaller Element
on both sides.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(N) |
Interview One-Liner
Compute the previous and next smaller element for every bar using a monotonic increasing stack, then calculate the maximum rectangle using
height × width.
Pattern Learned
Largest Rectangle
↓
Need Expansion
↓
Nearest Smaller Elements
↓
Monotonic Stack
Similar Problems
- Largest Rectangle in Histogram
- Maximal Rectangle
- Next Smaller Element
- Previous Smaller Element
- Sum of Subarray Minimums
Memory Trick
Think:
Current Bar
↓
Previous Smaller
↓
Next Smaller
↓
Width
↓
Area
Mental Model
Area
=
Height
×
Width
Width
=
Next Smaller
-
Previous Smaller
-
1
Whenever you hear:
"Largest Rectangle in Histogram"
your brain should immediately think:
Previous Smaller + Next Smaller + Monotonic Stack
SOCIAL SHARE CARD GENERATOR