Largest Sub-Square in a Binary Array

Based on the “largest square in a histogram” 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.

Largest rectangle in a histogram. (C) GeeksForGeeks.com – Shown under a FAIR USE exemption to the DMCA for works relating to public knowledge.

Using a “waterfall” incrementing operation, we arrive at the code shown below.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define bool int
#define R 20
#define C 20

void printMaxSubSquare(bool M[R][C]) {
   int i,j;
   int S[R][C];
   int max_of_s, max_i, max_j;

   /* Set first column of S[][]*/
   for(i = 0; i < R; i++)
      S[i][0] = M[i][0];

   /* Set first row of S[][]*/
   for(j = 0; j < C; j++)
      S[0][j] = M[0][j];

   /* Construct other entries of S[][]*/
   for(i = 1; i < R; i++) {
      for(j = 1; j < C; j++) {
         if(M[i][j] == 1)
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
         else
            S[i][j] = 0;
      }
   }

   /* Find the maximum entry, and indexes of maximum entry
      in S[][] */
   max_of_s = S[0][0]; max_i = 0; max_j = 0;
   for(i = 0; i < R; i++)
   {
      for(j = 0; j < C; j++)
      {
         if(max_of_s < S[i][j])
         {
            max_of_s = S[i][j];
            max_i = i;
            max_j = j;
         }
      }
   }
   printf("max_of_s:%d - max_i:%d - max_j:%d\n", max_of_s, max_i, max_j);

   printf("\n Maximum size sub-matrix is: \n");
   for(i = max_i; i > max_i - max_of_s; i--)
   {
      for(j = max_j; j > max_j - max_of_s; j--)
      {
         printf("%d ", M[i][j]);
      }
      printf("\n");
   }

   /* Print a prettier description of our result */
   for (i=0; i<R; i++) {
      for (j=0; j<C; j++) {
         if ((i > max_i - max_of_s) && (i <= max_i) && (j > max_j - max_of_s) && (j <= max_j)) {
            printf("# ");
         } else {
            printf(". ");
         }
      }
      printf("\n");
   }
   printf("\n");
   /* Print out the sum column */
   for (i=0; i<R; i++) {
      for (j=0; j<C; j++) {
         printf("%d ", S[i][j]);
      }
      printf("\n");
   }
   printf("\n");

}

/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */
int min(int a, int b, int c)
{
   int m = a;
   if (m > b)
      m = b;
   if (m > c)
      m = c;
   return m;
}

/* Driver function to test above functions */
int main()
{
   int i, j;
   const int bias = 2;   /* Set to "2" for a 50/50 random chance; Higher bias
                         * means a greater chance of the value being set to
                         * true, and a larger sub-square being likely.
                         */
   bool M[R][C] = { 0 };
   /*
   bool M[R][C] =  {{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}};
   */
   srand(time(NULL));
   for (i=0; i<R; i++) {
      for (j=0; j<C; j++) {
         M[i][j] = (rand() % bias)>=(bias-1)?0:1;
      }
   }
   /* print overall square */
   for (i=0; i<R; i++) {
      for (j=0; j<C; j++) {
         printf("%d ", M[i][j]);
      }
      printf("\n");
   }
   printf("\n");

   printMaxSubSquare(M);
   //getchar();
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

#include <stdio.h>

#include <time.h>

#include <stdlib.h>

#define bool int

#define R 20

#define C 20

void printMaxSubSquare(bool M[R][C]) {

int i,j;

int S[R][C];

int max_of_s, max_i, max_j;

/* Set first column of S[][]*/

for(i = 0; i < R; i++)

S[i][0] = M[i][0];

/* Set first row of S[][]*/

for(j = 0; j < C; j++)

S[0][j] = M[0][j];

/* Construct other entries of S[][]*/

for(i = 1; i < R; i++) {

for(j = 1; j < C; j++) {

if(M[i][j] == 1)

S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;

else

S[i][j] = 0;

}

/* Find the maximum entry, and indexes of maximum entry

in S[][] */

max_of_s = S[0][0]; max_i = 0; max_j = 0;

for(i = 0; i < R; i++)

{

for(j = 0; j < C; j++)

{

if(max_of_s < S[i][j])

{

max_of_s = S[i][j];

max_i = i;

max_j = j;

}

printf("max_of_s:%d - max_i:%d - max_j:%d\n", max_of_s, max_i, max_j);

printf("\n Maximum size sub-matrix is: \n");

for(i = max_i; i > max_i - max_of_s; i--)

{

for(j = max_j; j > max_j - max_of_s; j--)

{

printf("%d ", M[i][j]);

}

printf("\n");

}

/* Print a prettier description of our result */

for (i=0; i<R; i++) {

for (j=0; j<C; j++) {

if ((i > max_i - max_of_s) && (i <= max_i) && (j > max_j - max_of_s) && (j <= max_j)) {

printf("# ");

} else {

printf(". ");

}

printf("\n");

}

printf("\n");

/* Print out the sum column */

for (i=0; i<R; i++) {

for (j=0; j<C; j++) {

printf("%d ", S[i][j]);

}

printf("\n");

}

printf("\n");

}

/* UTILITY FUNCTIONS */

/* Function to get minimum of three values */

int min(int a, int b, int c)

{

int m = a;

if (m > b)

m = b;

if (m > c)

m = c;

return m;

}

/* Driver function to test above functions */

int main()

{

int i, j;

const int bias = 2; /* Set to "2" for a 50/50 random chance; Higher bias

* means a greater chance of the value being set to

* true, and a larger sub-square being likely.

bool M[R][C] = { 0 };

bool M[R][C] = {{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}};

srand(time(NULL));

for (i=0; i<R; i++) {

for (j=0; j<C; j++) {

M[i][j] = (rand() % bias)>=(bias-1)?0:1;

}

/* print overall square */

for (i=0; i<R; i++) {

for (j=0; j<C; j++) {

printf("%d ", M[i][j]);

}

printf("\n");

}

printf("\n");

printMaxSubSquare(M);

//getchar();

}

The best part about this, is by manipulating the “bias” 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 “even” bias (ie: 50%), we see that the largest sub-square is often quite small.

0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0
1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 0 1 1
0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1
0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0
0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0
1 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1
0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0
0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0
1 0 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0
1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0
1 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 0
1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0
1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 1
1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1
1 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 0 1 0 0
0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0
1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0

max_of_s:2 - max_i:1 - max_j:7

 Maximum size sub-matrix is:
1 1
1 1
. . . . . . # # . . . . . . . . . . . .
. . . . . . # # . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .

0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0
1 1 1 1 0 1 1 2 2 2 0 1 1 1 0 0 1 0 1 1
0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 2
0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0
0 1 1 1 2 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0
1 1 2 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1
0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 2 2 0
0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0
1 0 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0
1 0 1 0 0 1 2 0 1 0 1 0 1 1 0 1 1 0 1 0
1 1 0 0 0 0 1 1 0 0 1 0 1 2 1 0 1 1 1 0
1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 2 2 0
1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 1
1 2 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1
1 1 1 0 1 2 1 0 0 0 1 0 0 1 2 2 0 1 0 0
0 0 0 0 0 1 2 1 0 0 1 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 1 0 1 1 2 0 0 0 0 1 1 1 1
0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0
1 1 1 0 1 2 2 2 0 1 1 0 1 1 0 1 0 0 1 0

0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0

1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 0 1 1

0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1

0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0

0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0

1 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1

0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0

0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0

1 0 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0

1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0

1 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 0

1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0

1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 1

1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0

1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1

1 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 0 1 0 0

0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0

1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1

0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0

1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0

max_of_s:2 - max_i:1 - max_j:7

Maximum size sub-matrix is:

1 1

. . . . . . # # . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0

1 1 1 1 0 1 1 2 2 2 0 1 1 1 0 0 1 0 1 1

0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 2

0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0

0 1 1 1 2 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0

1 1 2 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1

0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 2 2 0

0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0

1 0 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0

1 0 1 0 0 1 2 0 1 0 1 0 1 1 0 1 1 0 1 0

1 1 0 0 0 0 1 1 0 0 1 0 1 2 1 0 1 1 1 0

1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 2 2 0

1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 1

1 2 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0

1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1

1 1 1 0 1 2 1 0 0 0 1 0 0 1 2 2 0 1 0 0

0 0 0 0 0 1 2 1 0 0 1 1 0 0 0 0 0 1 0 0

1 1 0 0 0 0 0 1 0 1 1 2 0 0 0 0 1 1 1 1

0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0

1 1 1 0 1 2 2 2 0 1 1 0 1 1 0 1 0 0 1 0

While with a modified bias (80% in the case below) we get much larger sub-squares.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

max_of_s:14 - max_i:19 - max_j:18


. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .
. . . . . # # # # # # # # # # # # # # .

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
1 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 3 0 1 2 3 4 5 5 5 5 5 5 5 5 5 5 5 5
1 2 3 1 1 2 3 4 5 6 6 6 6 0 1 2 3 4 5 6
1 2 3 2 2 2 3 4 5 6 7 7 7 1 1 2 3 4 5 6
1 2 3 3 3 3 3 4 5 6 7 8 8 2 2 2 3 4 5 6
1 2 3 4 4 4 4 4 5 6 7 8 9 3 3 3 3 4 5 6
1 2 3 4 5 5 5 5 5 6 7 8 9 4 4 4 4 4 5 6
1 2 3 4 5 6 6 6 6 6 7 8 9 5 5 5 5 5 5 6
1 2 3 4 5 6 7 7 7 7 7 8 9 6 6 6 6 6 6 6
1 2 3 4 5 6 7 8 8 8 8 8 9 7 7 7 7 7 7 7
1 2 3 4 5 6 7 8 9 9 9 9 9 8 8 8 8 8 8 8
1 2 3 4 5 6 7 8 9 10 10 10 10 9 9 9 9 9 9 9
1 0 1 2 3 4 5 6 7 8 9 10 11 10 10 10 10 10 10 10
1 1 1 2 0 1 2 3 4 5 6 7 8 9 10 11 11 11 11 11
1 2 2 2 0 1 2 3 4 5 6 7 8 9 10 11 12 12 12 12
1 2 3 3 1 1 2 3 4 5 6 7 8 9 10 11 12 13 13 13
1 2 3 4 2 2 2 3 4 5 6 7 8 9 10 11 12 13 14 14

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

max_of_s:14 - max_i:19 - max_j:18

. . . . . . . . . . . . . . . . . . . .

. . . . . # # # # # # # # # # # # # # .

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

1 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

1 2 3 0 1 2 3 4 5 5 5 5 5 5 5 5 5 5 5 5

1 2 3 1 1 2 3 4 5 6 6 6 6 0 1 2 3 4 5 6

1 2 3 2 2 2 3 4 5 6 7 7 7 1 1 2 3 4 5 6

1 2 3 3 3 3 3 4 5 6 7 8 8 2 2 2 3 4 5 6

1 2 3 4 4 4 4 4 5 6 7 8 9 3 3 3 3 4 5 6

1 2 3 4 5 5 5 5 5 6 7 8 9 4 4 4 4 4 5 6

1 2 3 4 5 6 6 6 6 6 7 8 9 5 5 5 5 5 5 6

1 2 3 4 5 6 7 7 7 7 7 8 9 6 6 6 6 6 6 6

1 2 3 4 5 6 7 8 8 8 8 8 9 7 7 7 7 7 7 7

1 2 3 4 5 6 7 8 9 9 9 9 9 8 8 8 8 8 8 8

1 2 3 4 5 6 7 8 9 10 10 10 10 9 9 9 9 9 9 9

1 0 1 2 3 4 5 6 7 8 9 10 11 10 10 10 10 10 10 10

1 1 1 2 0 1 2 3 4 5 6 7 8 9 10 11 11 11 11 11

1 2 2 2 0 1 2 3 4 5 6 7 8 9 10 11 12 12 12 12

1 2 3 3 1 1 2 3 4 5 6 7 8 9 10 11 12 13 13 13

1 2 3 4 2 2 2 3 4 5 6 7 8 9 10 11 12 13 14 14

GIASSA.NET

Engineering, DIY, and Everything Else

Largest Sub-Square in a Binary Array