#85
Maximal Rectangle
Hard Histogram per row
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a binary matrix of '0' and '1', return the area of the largest rectangle containing only '1's.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the largest all-'1' rectangle in a grid.
Why this works: treat each row as the floor of a histogram of consecutive 1s, then run "largest rectangle in histogram".
Example: rows build heights like [3, 1, 3, 2, 2]
histogram answer for that row = 6best over all rows = answer
✦Hints open one at a time
Treat each row as the floor of a histogram: height[c] = consecutive '1's ending at this row in column c.
Then each row is "Largest Rectangle in Histogram".
↗Approach
Update heights row by row (reset to 0 on '0'), run the monotonic-stack histogram routine, and keep the maximum.
</>Solution (Java)
import java.util.*;
class Solution {
public int maximalRectangle(char[][] matrix) {
int n = matrix[0].length, best = 0;
int[] heights = new int[n];
for (char[] row : matrix) {
for (int c = 0; c < n; c++) heights[c] = row[c] == '1' ? heights[c] + 1 : 0;
best = Math.max(best, largest(heights));
}
return best;
}
private int largest(int[] h) {
int best = 0;
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i <= h.length; i++) {
int cur = (i == h.length) ? 0 : h[i];
while (!st.isEmpty() && h[st.peek()] > cur) {
int height = h[st.pop()];
int width = st.isEmpty() ? i : i - st.peek() - 1;
best = Math.max(best, height * width);
}
st.push(i);
}
return best;
}
}!Common mistake
Not resetting the height to 0 when a '0' appears, which lets rectangles pass through zeros.
Complexity
- Time: O(m·n).
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon