![\"Maximum-size-square-sub-matrix-with-all-1s\"](\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Maximum-size-square-sub-matrix-with-all-1s.png\")
<\/p>\nGiven a binary matrix, find out the maximum size square sub-matrix with all 1s.<\/p>\n
For example, consider the below binary matrix.<\/p>\n
<\/p>\n
Algorithm:
\nLet 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.<\/p>\n
1) Construct a sum matrix S[R][C] for the given M[R][C].\r\n a)\tCopy first row and first columns as it is from M[][] to S[][]\r\n b)\tFor other entries, use following expressions to construct S[][]\r\n If M[i][j] is 1 then\r\n S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1\r\n Else \/*If M[i][j] is 0*\/\r\n S[i][j] = 0\r\n2) Find the maximum entry in S[R][C]\r\n3) Using the value and coordinates of maximum entry in S[i], print \r\n sub-matrix of M[][]<\/pre>\n[ad type=\u201dbanner\u201d]\nFor the given M[R][C] in above example, constructed S[R][C] would be:<\/p>\n
0 1 1 0 1\r\n 1 1 0 1 0\r\n 0 1 1 1 0\r\n 1 1 2 2 0\r\n 1 2 2 3 1\r\n 0 0 0 0 0<\/pre>\nThe 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.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u2013)%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\u2013)%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\u2033 message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
\nAuxiliary Space: O(m*n) where m is number of rows and n is number of columns in the given matrix.
\nAlgorithmic Paradigm: Dynamic Programming<\/p>\n[ad type=\u201dbanner\u201d]\n\u00a0<\/p>\n
\u00a0<\/p>\n
\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"
Maximum size square sub-matrix with all 1s – Dynamic Programming Given a binary matrix, find out the maximum size square sub-matrix with all 1s.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,70145],"tags":[72850,79162,79161,79167,72839,79164,79157,79166,79159,79163,79156,79160,79165,79158,79168,72852,72855,72853,72851],"class_list":["post-26574","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-dynamic-programming","tag-explain-dynamic-programming","tag-find-largest-sub-matrix-with-all-1s","tag-find-largest-sub-square-matrix-with-all-0s","tag-find-submatrix-in-matrix","tag-how-to-solve-dynamic-programming-problems","tag-maximum-area-rectangle-in-c","tag-maximum-size-rectangle-binary-sub-matrix-with-all-1s","tag-maximum-size-rectangle-of-all-1s","tag-maximum-size-rectangle-of-all-1s-dynamic-programming","tag-maximum-size-rectangular-submatrix-with-all-1s","tag-maximum-size-square-sub-matrix-with-all-1s","tag-maximum-size-square-sub-matrix-with-all-1s-example","tag-maximum-size-square-submatrix-with-all-1s-java","tag-maximum-sub-square-matrix-dynamic-programming","tag-maximum-sum-submatrix","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","tag-types-of-dynamic-programming","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26574","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26574"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26574\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26574"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26574"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26574"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}