{"id":26574,"date":"2017-12-20T21:45:40","date_gmt":"2017-12-20T16:15:40","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26574"},"modified":"2017-12-20T21:45:40","modified_gmt":"2017-12-20T16:15:40","slug":"maximum-size-square-sub-matrix-1s-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/maximum-size-square-sub-matrix-1s-2\/","title":{"rendered":"Maximum size square sub-matrix with all 1s"},"content":{"rendered":"<p>Given a binary matrix, find out the maximum size square sub-matrix with all 1s.<\/p>\n<p>For example, consider the below binary matrix.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"size-full wp-image-26577 aligncenter\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Maximum-size-square-sub-matrix-with-all-1s.png\" alt=\"Maximum-size-square-sub-matrix-with-all-1s\" width=\"417\" height=\"155\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Maximum-size-square-sub-matrix-with-all-1s.png 417w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Maximum-size-square-sub-matrix-with-all-1s-300x112.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Maximum-size-square-sub-matrix-with-all-1s-414x155.png 414w\" sizes=\"(max-width: 417px) 100vw, 417px\" \/><\/p>\n<p>Algorithm:<br \/>\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<pre>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=&#8221;banner&#8221;]\n<p>For the given M[R][C] in above example, constructed S[R][C] would be:<\/p>\n<pre>   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>\n<p>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.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C<\/span> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">#include&lt;stdio.h&gt;<br\/>#define bool int<br\/>#define R 6<br\/>#define C 5<br\/> <br\/>void printMaxSubSquare(bool M[R][C])<br\/>{<br\/>  int i,j;<br\/>  int S[R][C];<br\/>  int max_of_s, max_i, max_j; <br\/>  <br\/>  \/* Set first column of S[][]*\/<br\/>  for(i = 0; i &lt; R; i++)<br\/>     S[i][0] = M[i][0];<br\/>  <br\/>  \/* Set first row of S[][]*\/    <br\/>  for(j = 0; j &lt; C; j++)<br\/>     S[0][j] = M[0][j];<br\/>      <br\/>  \/* Construct other entries of S[][]*\/<br\/>  for(i = 1; i &lt; R; i++)<br\/>  {<br\/>    for(j = 1; j &lt; C; j++)<br\/>    {<br\/>      if(M[i][j] == 1) <br\/>        S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;<br\/>      else<br\/>        S[i][j] = 0;<br\/>    }    <br\/>  } <br\/>   <br\/>  \/* Find the maximum entry, and indexes of maximum entry <br\/>     in S[][] *\/<br\/>  max_of_s = S[0][0]; max_i = 0; max_j = 0;<br\/>  for(i = 0; i &lt; R; i++)<br\/>  {<br\/>    for(j = 0; j &lt; C; j++)<br\/>    {<br\/>      if(max_of_s &lt; S[i][j])<br\/>      {<br\/>         max_of_s = S[i][j];<br\/>         max_i = i; <br\/>         max_j = j;<br\/>      }        <br\/>    }                 <br\/>  }     <br\/>   <br\/>  printf(&quot;\\n Maximum size sub-matrix is: \\n&quot;);<br\/>  for(i = max_i; i &gt; max_i - max_of_s; i--)<br\/>  {<br\/>    for(j = max_j; j &gt; max_j - max_of_s; j--)<br\/>    {<br\/>      printf(&quot;%d &quot;, M[i][j]);<br\/>    }  <br\/>    printf(&quot;\\n&quot;);<br\/>  }  <br\/>}     <br\/> <br\/>\/* UTILITY FUNCTIONS *\/<br\/>\/* Function to get minimum of three values *\/<br\/>int min(int a, int b, int c)<br\/>{<br\/>  int m = a;<br\/>  if (m &gt; b) <br\/>    m = b;<br\/>  if (m &gt; c) <br\/>    m = c;<br\/>  return m;<br\/>}<br\/> <br\/>\/* Driver function to test above functions *\/<br\/>int main()<br\/>{<br\/>  bool M[R][C] =  {{0, 1, 1, 0, 1}, <br\/>                   {1, 1, 0, 1, 0}, <br\/>                   {0, 1, 1, 1, 0},<br\/>                   {1, 1, 1, 1, 0},<br\/>                   {1, 1, 1, 1, 1},<br\/>                   {0, 0, 0, 0, 0}};<br\/>                <br\/>  printMaxSubSquare(M);<br\/>  getchar();  <br\/>}  <\/code><\/pre> <\/div>\n<p>Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.<br \/>\nAuxiliary Space: O(m*n) where m is number of rows and n is number of columns in the given matrix.<br \/>\nAlgorithmic Paradigm: Dynamic Programming<\/p>\n[ad type=&#8221;banner&#8221;]\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Maximum size square sub-matrix with all 1s &#8211; 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}]}}