Prefix Sum — Maximal Rectangle
↗ LeetCode: Maximal Rectangle · Hard · pattern chapter →
Asked atAmazonGoogleMetaMicrosoft
Given a binary matrix, find the largest rectangle containing only 1s.
Example 1 — mat=[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] → 6Example 2 — mat=[["0"]] → 0Example 3 — mat=[["1"]] → 1
Constraints — 1 ≤ m, n ≤ 200; entries '0'/'1'. Brute enumerates every rectangle in O(m²·n²) = 10⁸ ops at m=n=100 (borderline). Reduce each row to histogram + monotonic stack is O(m·n) = 10⁴ ops = <1 min even at 10⁵ queries.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Every submatrix
O(m³·n³). TLE.
Approach 2 — Row heights + Largest Rectangle in Histogram (canonical)
Insight. For each row i, build heights[j] = number of consecutive 1s ending at mat[i][j]. Then apply Largest Rectangle in Histogram to that heights array. Max across all rows.
java
int maximalRectangle(char[][] mat) {
if (mat.length == 0) return 0;
int m = mat.length, n = mat[0].length, best = 0;
int[] h = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) h[j] = mat[i][j] == '1' ? h[j] + 1 : 0;
best = Math.max(best, largestRect(h));
}
return best;
}
int largestRect(int[] h) {
Deque<Integer> st = new ArrayDeque<>();
int best = 0, n = h.length;
for (int i = 0; i <= n; i++) {
int val = i == n ? 0 : h[i];
while (!st.isEmpty() && h[st.peek()] > val) {
int t = st.pop();
int w = st.isEmpty() ? i : i - st.peek() - 1;
best = Math.max(best, h[t] * w);
}
st.push(i);
}
return best;
}Execution Trace
Complexity — Time O(m·n); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Enumerate submatrices | O(m³·n³) | O(1) | baseline |
| Rows + histogram stack | O(m·n) | O(n) | canonical |
When to use which
- Binary matrix, largest rectangle of 1s → row-height + histogram stack.
- Only squares → simpler DP (see Maximal Square).
- "Count submatrices with X" → row-collapse + 1D template.
AI Study CompanionBeta
Related problems
Was this page helpful?