Given a binary matrix filled with 0 and 1, find the largest rectangle containing only 1s and return its area.
Input: [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] → Output: 6
Build height histogram row by row (heights[j] = consecutive 1s above including current row). Apply "Largest Rectangle in Histogram" for each row.
- Maintain heights[]: if matrix[i][j]==1: heights[j]++; else heights[j]=0.
- For each row: largestRectangleInHistogram(heights).
- Track global max.
import java.util.*;
class Solution {
public int maximalRectangle(char[][] matrix) {
int n = matrix[0].length, max = 0;
int[] heights = new int[n];
for (char[] row : matrix) {
for (int j=0;j<n;j++) heights[j] = row[j]=='1' ? heights[j]+1 : 0;
max = Math.max(max, largestRect(heights));
}
return max;
}
private int largestRect(int[] h) {
Deque<Integer> stack = new ArrayDeque<>();
int max=0, n=h.length;
for (int i=0;i<=n;i++) {
int cur=i==n?0:h[i];
while (!stack.isEmpty()&&h[stack.peek()]>cur) {
int height=h[stack.pop()], width=stack.isEmpty()?i:i-stack.peek()-1;
max=Math.max(max,height*width);
}
stack.push(i);
}
return max;
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(N)