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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
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 |
While with a modified bias (80% in the case below) we get much larger sub-squares.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 |