Java Program To Solve Maximum Size Rectangle In Binary Matrix

Given a binary matrix, find max rectangle with all 1’s.

A : [  1 1 1 0
0 1 1 0
1 1 1 0
]

Output : 6

Dynamic programming can help us here. For this, we can use maximum size rectangle in a histogram as a sub-problem. The idea is for each row we will calculate the histogram. If current [row][column] value is 0, then current histogram [column] value will become 0. If current [row][column] value is 1, then histogram [column] value will be incremented by 1. Then we will apply max rectangle histogram sub-problem & check for maximum area within the histogram.

The time complexity of this Java solution will be O(n * m) where n is the size of rows & m is the size of columns. We have a nested loop. For each traversal of outer loop, we do m traversal to calculate the current histogram & then we find the largest rectangle in the histogram in O(m) time complexity. So basically it is n * (m + m) which is O(n*m).

Space complexity is O(m) as we need m space for tracking current histogram & another m space used by stack for calculating largest rectangle within a histogram.

Here is the Java implementation to find the largest area of a binary matrix with all ones.

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
public int maximalRectangle(ArrayList<ArrayList<Integer>> A) {

List<Integer> result = new ArrayList<Integer>();
for(int i=0; i<A.get(0).size(); i++){
result.add(0);
}

int maxArea = 0;

for(int i=0; i<A.size(); i++){
ArrayList<Integer> currentRow = A.get(i);
for(int j=0; j<currentRow.size(); j++){
if(currentRow.get(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;
}
}

Leave a Comment