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.