We will solve LeetCode problem “85. Maximal Rectangle” here. The problem states that:
Given a rows x cols binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.
Input: [ 1 1 1 0
0 1 1 0
1 1 1 0
]
Output: 6
Does the above input look like a histogram? It kind of does. It reminds me of a problem that we solved earlier “largest rectangle in a histogram“. Our input is not exactly a histogram, though the structure looks like one. Let us convert it to a histogram. The idea is simple. We will start at the top row & go till bottom row one by one. At any given row, we will check each element from left to right. If an element is “0”, the base for that column is 0. So corresponding histogram value is 0. If an element is “1”, we will add the value from the above cell to it. Why would we do that? From the current row element we will know the base. If base is 1, we need to add the value from one level up to construct histogram for that column.
Our first row: 1 1 1 0 Histogram at first row: 1 1 1 0 Second row: 0 1 1 0 Histogram at second row: 0 2 2 0 Third row: 1 1 1 0 Histogram at third row: 1 3 3 0
So after converting each row to a histogram, we have the following array:
1 1 1 0
0 2 2 0
1 3 3 0
We can apply the maximum rectangle in a histogram problem here. At each row, we will find the histogram at that level. Then we will find the maximum rectangle area for that histogram & track the max value across all levels.
Here is the complete Java code for the above LeetCode problem.
class Solution {
public int maximalRectangle(char[][] matrix) {
List<Integer> result = new ArrayList<Integer>();
for(int i=0; i<matrix[0].length; i++){
result.add(0);
}
int maxArea = 0;
for(int i=0; i<matrix.length; i++){
char[] currentRow = matrix[i];
for(int j=0; j<currentRow.length; j++){
if(currentRow[j] == '1'){
result.set(j, result.get(j) + 1);
} else {
result.set(j, 0);
}
}
maxArea = findMaxArea(result, maxArea);
}
return maxArea;
}
// find maxArea of currently computed row using histogram
public int findMaxArea(List<Integer> result, int maxArea) {
Stack<Integer> stack = new Stack<Integer>();
int i = 0;
for(; i<result.size();){
if(stack.isEmpty() || result.get(stack.peek()) <= result.get(i)){
stack.push(i);
i++;
} else {
int index = stack.pop();
int leftBound = !stack.empty() ? stack.peek() : -1;
int rightBound = i;
int currentArea = (rightBound - leftBound - 1) * result.get(index);
if(currentArea > maxArea){
maxArea = currentArea;
}
}
}
while(!stack.isEmpty()){
int index = stack.pop();
int leftBound = !stack.empty() ? stack.peek() : -1;
int rightBound = i;
int currentArea = (rightBound - leftBound - 1) * result.get(index);
if(currentArea > maxArea){
maxArea = currentArea;
}
}
return maxArea;
}
}Time complexity: If we have m rows, we will calculate largest rectangle in histogram m times. Suppose each row has n columns. Solution to find maximum rectangle in a histogram is linear. Also histogram construction at each row level is linear. So it takes O(n) time complexity to find largest rectangle in histogram at each level. Overall time complexity for calculating largest rectangle in all histograms would be O(m * n). So total time complexity of our solution is O(m * n).
Space complexity: We are using n extra space to hold the histogram array at each level. Also we might need extra n space for the stack used at each level to find maximum rectangle in a histogram. So space complexity of the solution is O(n).