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;
    }
}

Comments