This page explains Java solution to problem Maximal Rectangle
using Stack
data structure.
Given a 2D binary matrix filled with 0's
and 1's
, find the largest rectangle containing only 1's
and return its area.
Input:
Input: [
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
package com.vc.hard;
import java.util.*;
class MaximalRectangle {
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[] row = new int[n];
int maxLength = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == '1') row[j] += 1;
else row[j] = 0;
}
maxLength = Math.max(maxLength, maxRectangle(row));
}
return maxLength;
}
private int maxRectangle(int[] heights) {
Stack<Integer> st = new Stack<>();
st.push(-1);
int maxLength = 0;
for(int i = 0; i < heights.length; i++) {
while(st.peek() != -1 && heights[st.peek()] > heights[i]) {
maxLength = Math.max(maxLength, heights[st.pop()] * (i - st.peek() - 1));
}
st.push(i);
}
while(st.peek() != -1) {
maxLength = Math.max(maxLength, heights[st.pop()] * (heights.length - st.peek() - 1));
}
return maxLength;
}
}
O(M * N) Where
M is total number of Rows in an input array
N is total number of Cols in an input array
O(N) Where
N is total number of Cols in an input array