Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
GeeksforGeeks
Input:
[
["1", "0", "1", "0", "0"],
["1", "0", "1", "1", "1"],
["1", "1", "1", "1", "1"],
["1", "0", "0", "1", "0"]
]
Output: 6
Last updated
Was this helpful?
Was this helpful?
/**
* Time complexity : O(row*column)
* Space complexity : O(column)
*/
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix == null ||
matrix.length == 0 ||
matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[] heights = new int[n];
int maxRect = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
int value = matrix[i][j]-'0';
heights[j] = (value == 0)? 0: (value + heights[j]);
}
maxRect = Math.max(maxRect, largestRectangleArea(heights));
}
return maxRect;
}
private int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int i = 0, area = 0;
while(i < heights.length) {
if(stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
stack.add(i++);
} else {
area = Math.max(area, calculateArea(stack, heights, i));
}
}
while(!stack.isEmpty()) {
area = Math.max(area, calculateArea(stack, heights, i));
}
return area;
}
private int calculateArea(Stack<Integer> stack, int[] heights, int i) {
int height = heights[stack.pop()];
int weight = (stack.isEmpty())? i: (i-stack.peek()-1);
return height * weight;
}
}