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