{"id":1203,"date":"2015-05-06T19:14:13","date_gmt":"2015-05-07T02:14:13","guid":{"rendered":"http:\/\/www.giassa.net\/?page_id=1203"},"modified":"2025-08-24T08:03:52","modified_gmt":"2025-08-24T15:03:52","slug":"largest-sub-square-in-a-binary-array","status":"publish","type":"page","link":"https:\/\/www.giassa.net\/?page_id=1203","title":{"rendered":"Largest Sub-Square in a Binary Array"},"content":{"rendered":"<p>Based on the <a href=\"http:\/\/www.geeksforgeeks.org\/largest-rectangle-under-histogram\/\">&#8220;largest square in a histogram&#8221;<\/a> problem (shown below), the goal is to analyze a binary 2D array consisting of ones and zeroes, and find the largest square section of the array that contains ones. This is useful for a number of tasks in statistics and image processing.<\/p>\n<div style=\"width: 567px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"\" src=\"http:\/\/www.geeksforgeeks.org\/wp-content\/uploads\/histogram1.png\" alt=\"\" width=\"557\" height=\"521\" \/><p class=\"wp-caption-text\">Largest rectangle in a histogram. (C) GeeksForGeeks.com &#8211; Shown under a FAIR USE exemption to the DMCA for works relating to public knowledge.<\/p><\/div>\n<p>&nbsp;<\/p>\n<p>Using a &#8220;waterfall&#8221; incrementing operation, we arrive at the code shown below.<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:c decode:true\" title=\"Largest square detection in a binary array\">\r\n#include &lt;stdio.h&gt;\r\n#include &lt;time.h&gt;\r\n#include &lt;stdlib.h&gt;\r\n\r\n#define bool int\r\n#define R 20\r\n#define C 20\r\n\r\nvoid printMaxSubSquare(bool M[R][C]) {\r\n   int i,j;\r\n   int S[R][C];\r\n   int max_of_s, max_i, max_j;\r\n\r\n   \/* Set first column of S[][]*\/\r\n   for(i = 0; i &lt; R; i++)\r\n      S[i][0] = M[i][0];\r\n\r\n   \/* Set first row of S[][]*\/\r\n   for(j = 0; j &lt; C; j++)\r\n      S[0][j] = M[0][j];\r\n\r\n   \/* Construct other entries of S[][]*\/\r\n   for(i = 1; i &lt; R; i++) {\r\n      for(j = 1; j &lt; C; j++) {\r\n         if(M[i][j] == 1)\r\n            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;\r\n         else\r\n            S[i][j] = 0;\r\n      }\r\n   }\r\n\r\n   \/* Find the maximum entry, and indexes of maximum entry\r\n      in S[][] *\/\r\n   max_of_s = S[0][0]; max_i = 0; max_j = 0;\r\n   for(i = 0; i &lt; R; i++)\r\n   {\r\n      for(j = 0; j &lt; C; j++)\r\n      {\r\n         if(max_of_s &lt; S[i][j])\r\n         {\r\n            max_of_s = S[i][j];\r\n            max_i = i;\r\n            max_j = j;\r\n         }\r\n      }\r\n   }\r\n   printf(\"max_of_s:%d - max_i:%d - max_j:%d\\n\", max_of_s, max_i, max_j);\r\n\r\n   printf(\"\\n Maximum size sub-matrix is: \\n\");\r\n   for(i = max_i; i &gt; max_i - max_of_s; i--)\r\n   {\r\n      for(j = max_j; j &gt; max_j - max_of_s; j--)\r\n      {\r\n         printf(\"%d \", M[i][j]);\r\n      }\r\n      printf(\"\\n\");\r\n   }\r\n\r\n   \/* Print a prettier description of our result *\/\r\n   for (i=0; i&lt;R; i++) {\r\n      for (j=0; j&lt;C; j++) {\r\n         if ((i &gt; max_i - max_of_s) &amp;&amp; (i &lt;= max_i) &amp;&amp; (j &gt; max_j - max_of_s) &amp;&amp; (j &lt;= max_j)) {\r\n            printf(\"# \");\r\n         } else {\r\n            printf(\". \");\r\n         }\r\n      }\r\n      printf(\"\\n\");\r\n   }\r\n   printf(\"\\n\");\r\n   \/* Print out the sum column *\/\r\n   for (i=0; i&lt;R; i++) {\r\n      for (j=0; j&lt;C; j++) {\r\n         printf(\"%d \", S[i][j]);\r\n      }\r\n      printf(\"\\n\");\r\n   }\r\n   printf(\"\\n\");\r\n\r\n}\r\n\r\n\/* UTILITY FUNCTIONS *\/\r\n\/* Function to get minimum of three values *\/\r\nint min(int a, int b, int c)\r\n{\r\n   int m = a;\r\n   if (m &gt; b)\r\n      m = b;\r\n   if (m &gt; c)\r\n      m = c;\r\n   return m;\r\n}\r\n\r\n\/* Driver function to test above functions *\/\r\nint main()\r\n{\r\n   int i, j;\r\n   const int bias = 2;   \/* Set to \"2\" for a 50\/50 random chance; Higher bias\r\n                         * means a greater chance of the value being set to\r\n                         * true, and a larger sub-square being likely.\r\n                         *\/\r\n   bool M[R][C] = { 0 };\r\n   \/*\r\n   bool M[R][C] =  {{0, 1, 1, 0, 1},\r\n      {1, 1, 0, 1, 0},\r\n      {0, 1, 1, 1, 0},\r\n      {1, 1, 1, 1, 0},\r\n      {1, 1, 1, 1, 1},\r\n      {0, 0, 0, 0, 0}};\r\n   *\/\r\n   srand(time(NULL));\r\n   for (i=0; i&lt;R; i++) {\r\n      for (j=0; j&lt;C; j++) {\r\n         M[i][j] = (rand() % bias)&gt;=(bias-1)?0:1;\r\n      }\r\n   }\r\n   \/* print overall square *\/\r\n   for (i=0; i&lt;R; i++) {\r\n      for (j=0; j&lt;C; j++) {\r\n         printf(\"%d \", M[i][j]);\r\n      }\r\n      printf(\"\\n\");\r\n   }\r\n   printf(\"\\n\");\r\n\r\n   printMaxSubSquare(M);\r\n   \/\/getchar();\r\n}\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>The best part about this, is by manipulating the &#8220;bias&#8221; variable, we can control the average number of ones versus zeros in the array, allowing us to see a number of different potential outcomes. With an &#8220;even&#8221; bias (ie: 50%), we see that the largest sub-square is often quite small.<\/p>\n<pre class=\"lang:c decode:true \">0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0\r\n1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 0 1 1\r\n0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1\r\n0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0\r\n0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0\r\n1 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1\r\n0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0\r\n0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0\r\n1 0 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0\r\n1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0\r\n1 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 0\r\n1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0\r\n1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 1\r\n1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0\r\n1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1\r\n1 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 0 1 0 0\r\n0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0\r\n1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1\r\n0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0\r\n1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0\r\n\r\nmax_of_s:2 - max_i:1 - max_j:7\r\n\r\n Maximum size sub-matrix is:\r\n1 1\r\n1 1\r\n. . . . . . # # . . . . . . . . . . . .\r\n. . . . . . # # . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n\r\n0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0\r\n1 1 1 1 0 1 1 2 2 2 0 1 1 1 0 0 1 0 1 1\r\n0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 2\r\n0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0\r\n0 1 1 1 2 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0\r\n1 1 2 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1\r\n0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 2 2 0\r\n0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0\r\n1 0 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0\r\n1 0 1 0 0 1 2 0 1 0 1 0 1 1 0 1 1 0 1 0\r\n1 1 0 0 0 0 1 1 0 0 1 0 1 2 1 0 1 1 1 0\r\n1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 2 2 0\r\n1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 1\r\n1 2 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0\r\n1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1\r\n1 1 1 0 1 2 1 0 0 0 1 0 0 1 2 2 0 1 0 0\r\n0 0 0 0 0 1 2 1 0 0 1 1 0 0 0 0 0 1 0 0\r\n1 1 0 0 0 0 0 1 0 1 1 2 0 0 0 0 1 1 1 1\r\n0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0\r\n1 1 1 0 1 2 2 2 0 1 1 0 1 1 0 1 0 0 1 0<\/pre>\n<p>&nbsp;<\/p>\n<p>While with a modified bias (80% in the case below) we get much larger sub-squares.<\/p>\n<pre class=\"lang:default decode:true  \">1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n\r\nmax_of_s:14 - max_i:19 - max_j:18\r\n\r\n\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n. . . . . # # # # # # # # # # # # # # .\r\n\r\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2\r\n1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3\r\n1 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4\r\n1 2 3 0 1 2 3 4 5 5 5 5 5 5 5 5 5 5 5 5\r\n1 2 3 1 1 2 3 4 5 6 6 6 6 0 1 2 3 4 5 6\r\n1 2 3 2 2 2 3 4 5 6 7 7 7 1 1 2 3 4 5 6\r\n1 2 3 3 3 3 3 4 5 6 7 8 8 2 2 2 3 4 5 6\r\n1 2 3 4 4 4 4 4 5 6 7 8 9 3 3 3 3 4 5 6\r\n1 2 3 4 5 5 5 5 5 6 7 8 9 4 4 4 4 4 5 6\r\n1 2 3 4 5 6 6 6 6 6 7 8 9 5 5 5 5 5 5 6\r\n1 2 3 4 5 6 7 7 7 7 7 8 9 6 6 6 6 6 6 6\r\n1 2 3 4 5 6 7 8 8 8 8 8 9 7 7 7 7 7 7 7\r\n1 2 3 4 5 6 7 8 9 9 9 9 9 8 8 8 8 8 8 8\r\n1 2 3 4 5 6 7 8 9 10 10 10 10 9 9 9 9 9 9 9\r\n1 0 1 2 3 4 5 6 7 8 9 10 11 10 10 10 10 10 10 10\r\n1 1 1 2 0 1 2 3 4 5 6 7 8 9 10 11 11 11 11 11\r\n1 2 2 2 0 1 2 3 4 5 6 7 8 9 10 11 12 12 12 12\r\n1 2 3 3 1 1 2 3 4 5 6 7 8 9 10 11 12 13 13 13\r\n1 2 3 4 2 2 2 3 4 5 6 7 8 9 10 11 12 13 14 14<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Based on the &#8220;largest square in a histogram&#8221; problem (shown below), the goal is to analyze a binary 2D array consisting of ones and zeroes, and find the largest square section of the array that contains ones. This is useful &hellip; <a href=\"https:\/\/www.giassa.net\/?page_id=1203\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1075,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1203","page","type-page","status-publish","hentry"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1203","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.giassa.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1203"}],"version-history":[{"count":2,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1203\/revisions"}],"predecessor-version":[{"id":1205,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1203\/revisions\/1205"}],"up":[{"embeddable":true,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1075"}],"wp:attachment":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1203"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}