Dynamic Programming - Find largest sub-square matrix with all 0s (Microsoft interview question)

1 users say they have been asked this quesiton in interview.
Difficulty Level:

Problem Statement

Given a square matrix (n*n) which contains only 1 and 0, find the largest sub-square matrix which only contains 0s. For example:
For example:

Input #1:
0 0 0 0
0 0 0 0
0 0 0 1
1 1 1 1 
The answer is 3.

Input #2:
1 1 1 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 1
1 1 1 1 0
The answer is 3.

Input #2:
1 1 1 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 1 1 1 0
The answer is 4.

Building the solution

Let us break down the problem to the smallest possible data set to get started. Consider a 1*1 matrix. For this matrix, if the element is 0, we definitely have a solution with answer as 1. Now, consider a 2*2 matrix and think can we extend our previous solution of 1*1 matrix to get a solution for this matrix. Have a look at the image below:

Largest sub square matrix with all 0 | EduSagar

Which means that if we consider the three neighbors (right, bottom-right and bottom) of an element which is 0, we can extend our solution. Put in other words - we can include those neighbors in our solution set. But we can do so only if all of the three neighbors are 0s. Now, consider the next bigger data set:

Largest sub square matrix with all 0 | EduSagar

In this case, we need to again consider all the three neighbors of 3 elements which we added to the solution in the previous step. So, basically this time we need to consider 3 neighbors(right, bottom-right and bottom) of 3 elements to extend our solutions. Like this, we can continue building up our solution until we find an element which is 1.
Now, what happens if we find an element which is 1 - we need to abandon our current solution and start building a solution from scratch for the next element which is 0, i.e. we will fall back to 1*1 matrix and start building the solution from there onwards. Off course, we need to save the answer to the previous solution somewhere, so that we can compare it with the new answer later on and figure out which is the largest sub-matrix. A rough pseudocode might look like this:

sub max_submatrix:
int max = 1
for i in 0..ROW:
    for j in 0..COL:
        // find the max you can get with x
        if arr[i][j] == 0:
            max_till_now = _max_submatrix(i, j, 1)
            if (max_till_now > max):
                max = max_till_now
        
    
sub _max_submatrix(int r, int c, int max):
    if (arr[r][c+1] == 0) && (arr[r+1][c+1] == 0) && (arr[r+1][c] == 0):
        x = _max_submatrix(r, c+1)
        y = _max_submatrix(r+1, c+1)
        z = _max_submatrix(r+1, c)
        
        return 1 + MIN(x,y,z)
    
    return max
So, if we want to approach the problem with a brute force solution, we need to iterate over the entire array. Pick an element if it is 0, then try to find out the maximum sub matrix starting from that element. For this we use _max_submatrix() subroutine. If an element has all the three neighbors as 0s, we recursively call _max_submatrix() to get the maximum sub-matrix formed by all these neighbors. Once we have the value for all of them, take the minimum of them and add 1 to it - this gives us the maximum sub-matrix formed with the current element as starting point. If any one of the neighbors is not zero, we can't include it in the current set of result and thus we return from here itself. 

Dynamic Programming Solution

The solution discussed above is highly inefficient as it solves same subproblem multiple number of times. If you remember basic rules for Dynamic Programming, this problem exhibits both the properties that any dynamic programming problem has. To solve this problem using Dynamic Programming, let us try to build the solution using the same approach as above, but in the bottom up manner:

Largest sub square matrix with all 0 | EduSagar

The idea is same as discussed above, just that the direction is reversed. A single element which is 0, always returns answer as 1. Now for 2*2 matrix as shown in the image above - if you look closely, the bottom-right element can be part of a solution sub-matrix only if all its three neighbors (top-left, top, left) are all 0s. If any of them is 1, this bottom-right element cannot extend the solution. Speaking generally - any element of an array which is 0, can act as the bottom-right corner and extend a solution only if all its three immediate neighbors are 0 as well. This leads us to the following recurrence equation:

F[i][j] = 1 + MIN(F[i-1][j], F[i-1][j-1], F[i][j-1]) if F[i][j] = 1
F[i][j] = 0 otherwise
We will use an array to store the intermediate values of F[i][j] and reuse this value later on when trying to solve the same subproblem again. Following is the Dynamic Programming Solution where F[ROW][COL] stores the final answer.

#include <stdio.h>
#include <stdlib.h>
#define ROW 6
#define COL 5

int min(int a, int b, int c)
{
    if (a < b) {
        return (a < c) ? a : c;
    } else {
        return (b < c) ? b : c;
    }
}

int main()
{
    int matrix[ROW][COL] = {
                {0, 0, 1, 1, 0}, 
                {0, 0, 0, 0, 1}, 
                {1, 0, 0, 0, 1},
                {0, 0, 0, 0, 1},
                {0, 0, 0, 0, 0},
                {1, 1, 1, 1, 1}};
                
    int output[ROW][COL] = {0};
    int i, j;
    int max = 1;
    
    for (i = 0; i < ROW; i++) {
        for (j = 0; j < COL; j++) {
            if (matrix[i][j] == 0)
                output[i][j] = 1;
        }
    }
    
    for (i = 1; i < ROW; i++) {
        for (j = 1; j < COL; j++) {
            if (output[i][j]) {
                output[i][j] = min(output[i-1][j-1], output[i-1][j], output[i][j-1]) + 1;
                if (output[i][j] > max)
                    max = output[i][j];
            }
        }
    }
    
    printf("The maximum size of sub-square matrix is : %d\n", max);

     return 0;
}
Feel the power of Dynamic Programming !! Although we used O(n2) of extra space, but the run time is drastically improved from exponential (for recursive solution) to O(n2). Do share your thoughts and comments if you feel something amiss.

comments powered by Disqus