PROGRAMMING INTERVIEWS

Question: Given a matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s.

Example: Consider the below matrix.

   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

The maximum square sub-matrix with all '1' bits is from (2,1) to (4,3)

    1  1  1
    1  1  1
    1  1  1

Answer: This is a classic Dynamic Programming problem. Lets calculate the maximum size square sub-matrix as we traverse the original matrix M[][]. We will use a auxiliary matrix S[][] of same size for memoization. S[i][j] represents size of the square sub-matrix with all 1s including M[i][j]. 'i' and 'j' will be the last row and column respectively in square sub-matrix.

How to calculate S[i][j]:
We should note that if M[i][j] is '0' then S[i][j] will obviously be '0'. If M[i][j] is '1' then S[i][j] depends on earlier values.

If M[i][j] is '1' then it will contribute to the all 1s square sub-matrix ending at either M[i][j-1] or M[i-1][j] or M[i-1][j-1]. If we visualize the conditions then, we will see:

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

How did we arrive at above relationship?
Note if we include M[i][j] in earlier calculated sub-matrix then we are adding S[i][j] elements from i^th row and j^th columns. They all should be '1' if we wanna include M[i][j]. On visualizing with some examples, readers will analyze why, minimum of 3 neighbors is taken.

For the given M[][] in above example, constructed S[][] would be:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  0
   1  2  2  3  1
   0  0  0  0  0

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.

Code:

#define ROW 10
#define COL 10

void FindMaxSubSquare(bool M[ROW][COL], int &max_i, int &max_j, int &size)
{
    int i,j;
    int S[ROW][COL];
 
    /* Set first column of S[][]*/
    for(i = 0; i < ROW; i++)
        S[i][0] = M[i][0];
 
    /* Set first row of S[][]*/
    for(j = 0; j < COL; j++)
        S[0][j] = M[0][j];
 
    /* Construct other entries of S[][]*/
    for(i = 1; i < ROW; i++)
    {
        for(j = 1; j < COL; 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[][] */
    size = S[0][0]; max_i = 0; max_j = 0;
    for(i = 0; i < ROW; i++)
    {
        for(j = 0; j < COL; j++)
        {
            if(size < S[i][j])
            {
                size = S[i][j];
                max_i = i;
                max_j = j;
            }
        }
    }     
    return
}

Complexity:
Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Space Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.

Note: Part of this post is taken from geeksforgeeks.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.