DP #30. Maximum Subsquare Matrix of all 1s - mbhushan/dynpro GitHub Wiki
(30). Maximum subsquare matrix of all 1s.
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
For example, consider the below binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
The maximum square sub-matrix with all set bits is
1 1 1
1 1 1
1 1 1
Formula:
if (M[i][j] == 0) {
T[i][j] = 0
} else {
T[i][j] = 1 + Min(T[i][j-1], T[i-1][j-1], T[i-1][j])
}
|
|
|
|
|
|
| M[][] |
0 |
1 |
1 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
| T[][] |
0 |
1 |
1 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
2 |
2 |
0 |
|
1 |
2 |
2 |
3 (ans) |
1 |
|
0 |
0 |
0 |
0 |
0 |
Max Subsquare Matrix
- Time Complexity: O(row*col)
- Space Complexity: O(row*col)