Find biggest submatrix which has only ones
Given
a matrix composed of 1s and 0s only, find the biggest submatrix
which is entirely composed of 1s only.
Solution:
If there were only cell in the matrix, then biggest submatrix is
that cell itself if it has a 1
Now,
if you introduce an extra column, the biggest submatrix can be on
length 2 if both of them are 1
i.e.
F(2) = 1+F(1)
So,
if we store the biggest submatrices ending at every index in the
matrix, then addition of row or a column (at k+1^{th}
position) can just consider the ones at row k and column k to see if
k+1 row or column will have bigger matrices.
Note:
It is difficult to say which matrix is bigger if we consider
nonsquare matrices also. Example: if 2 matrices have dimension, 4x4
and 3x5, both ending at index 5,5, then we would have to keep both of
them because addition of 6^{t}^{h}
row/column can result in 3x6, 4x5 or 4x5, 5x5 matrices at index 6,6
To
simplify, we will consider only those matrices which are square
matrices i.e. K by K matrices only. With this simplification, every
index can have maximum of only 1 submatrix
A
lookup matrix can be made into which we will incrementally store
maximum submatrices by adding one row/column at a time.
The
above figure explains the lookup relation:
lookup[i][j]
= 1 + min (
lookup[i][j1],
lookup[i1][j],
lookup[i1][j1]
)
With
the above observations, the code can be written as follows:
Order
for this solution is O(n^{2})
or O(maxRows x maxCols)
