Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
For example, consider the below binary matrix.
Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
[ad type=”banner”]
For the given M[R][C] in above example, constructed S[R][C] would be:
0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 2 2 0 1 2 2 3 1 0 0 0 0 0
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.
[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%23define%20bool%20int%0A%23define%20R%206%0A%23define%20C%205%0A%20%0Avoid%20printMaxSubSquare(bool%20M%5BR%5D%5BC%5D)%0A%7B%0A%20%20int%20i%2Cj%3B%0A%20%20int%20S%5BR%5D%5BC%5D%3B%0A%20%20int%20max_of_s%2C%20max_i%2C%20max_j%3B%20%0A%20%20%0A%20%20%2F*%20Set%20first%20column%20of%20S%5B%5D%5B%5D*%2F%0A%20%20for(i%20%3D%200%3B%20i%20%3C%20R%3B%20i%2B%2B)%0A%20%20%20%20%20S%5Bi%5D%5B0%5D%20%3D%20M%5Bi%5D%5B0%5D%3B%0A%20%20%0A%20%20%2F*%20Set%20first%20row%20of%20S%5B%5D%5B%5D*%2F%20%20%20%20%0A%20%20for(j%20%3D%200%3B%20j%20%3C%20C%3B%20j%2B%2B)%0A%20%20%20%20%20S%5B0%5D%5Bj%5D%20%3D%20M%5B0%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%0A%20%20%2F*%20Construct%20other%20entries%20of%20S%5B%5D%5B%5D*%2F%0A%20%20for(i%20%3D%201%3B%20i%20%3C%20R%3B%20i%2B%2B)%0A%20%20%7B%0A%20%20%20%20for(j%20%3D%201%3B%20j%20%3C%20C%3B%20j%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20if(M%5Bi%5D%5Bj%5D%20%3D%3D%201)%20%0A%20%20%20%20%20%20%20%20S%5Bi%5D%5Bj%5D%20%3D%20min(S%5Bi%5D%5Bj-1%5D%2C%20S%5Bi-1%5D%5Bj%5D%2C%20S%5Bi-1%5D%5Bj-1%5D)%20%2B%201%3B%0A%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20S%5Bi%5D%5Bj%5D%20%3D%200%3B%0A%20%20%20%20%7D%20%20%20%20%0A%20%20%7D%20%0A%20%20%20%0A%20%20%2F*%20Find%20the%20maximum%20entry%2C%20and%20indexes%20of%20maximum%20entry%20%0A%20%20%20%20%20in%20S%5B%5D%5B%5D%20*%2F%0A%20%20max_of_s%20%3D%20S%5B0%5D%5B0%5D%3B%20max_i%20%3D%200%3B%20max_j%20%3D%200%3B%0A%20%20for(i%20%3D%200%3B%20i%20%3C%20R%3B%20i%2B%2B)%0A%20%20%7B%0A%20%20%20%20for(j%20%3D%200%3B%20j%20%3C%20C%3B%20j%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20if(max_of_s%20%3C%20S%5Bi%5D%5Bj%5D)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20max_of_s%20%3D%20S%5Bi%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20max_i%20%3D%20i%3B%20%0A%20%20%20%20%20%20%20%20%20max_j%20%3D%20j%3B%0A%20%20%20%20%20%20%7D%20%20%20%20%20%20%20%20%0A%20%20%20%20%7D%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%7D%20%20%20%20%20%0A%20%20%20%0A%20%20printf(%22%5Cn%20Maximum%20size%20sub-matrix%20is%3A%20%5Cn%22)%3B%0A%20%20for(i%20%3D%20max_i%3B%20i%20%3E%20max_i%20-%20max_of_s%3B%20i–)%0A%20%20%7B%0A%20%20%20%20for(j%20%3D%20max_j%3B%20j%20%3E%20max_j%20-%20max_of_s%3B%20j–)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20printf(%22%25d%20%22%2C%20M%5Bi%5D%5Bj%5D)%3B%0A%20%20%20%20%7D%20%20%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%20%7D%20%20%0A%7D%20%20%20%20%20%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Function%20to%20get%20minimum%20of%20three%20values%20*%2F%0Aint%20min(int%20a%2C%20int%20b%2C%20int%20c)%0A%7B%0A%20%20int%20m%20%3D%20a%3B%0A%20%20if%20(m%20%3E%20b)%20%0A%20%20%20%20m%20%3D%20b%3B%0A%20%20if%20(m%20%3E%20c)%20%0A%20%20%20%20m%20%3D%20c%3B%0A%20%20return%20m%3B%0A%7D%0A%20%0A%2F*%20Driver%20function%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20bool%20M%5BR%5D%5BC%5D%20%3D%20%20%7B%7B0%2C%201%2C%201%2C%200%2C%201%7D%2C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B1%2C%201%2C%200%2C%201%2C%200%7D%2C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%201%2C%201%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B1%2C%201%2C%201%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B1%2C%201%2C%201%2C%201%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%200%2C%200%7D%7D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20printMaxSubSquare(M)%3B%0A%20%20getchar()%3B%20%20%0A%7D%20%20″ message=”C” highlight=”” provider=”manual”/]Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Auxiliary Space: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Algorithmic Paradigm: Dynamic Programming