Solve the problem of finding the Maximum Size Square Sub-Matrix with all 1s in a binary matrix using dynamic programming.?

The problem of finding the Maximum Size Square Sub-Matrix with all 1s in a binary matrix using dynamic programming can be solved using a bottom-up approach.

Let ‘maxSize‘ be the variable that holds the size of the largest square sub-matrix of all 1s that is found so far.

We can define a 2D array ‘dp[][]‘ such that ‘dp[i][j]‘ represents the size of the largest square sub-matrix with all 1s that has its bottom-right corner at ‘matrix[i][j]‘.

We can initialize the first row and first column of ‘dp[][]‘ with the corresponding values of ‘matrix[][]‘, since any square sub-matrix at the edges of the matrix can only have a size of 1.

Then, for each cell ‘dp[i][j]‘, if ‘matrix[i][j]‘ is 1, we can set ‘dp[i][j]‘ to ‘min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1‘. This is because the size of the largest square sub-matrix with all 1s that has its bottom-right corner at ‘matrix[i][j]‘ is determined by the minimum of its top, left, and diagonal neighbors.

As we fill in the ‘dp[][]‘ array, we can also update ‘maxSize‘ accordingly.

Here’s a Java implementation of the algorithm:

public int findMaxSquareSubmatrix(int[][] matrix) {
    int n = matrix.length;
    int m = matrix[0].length;
    int maxSize = 0;
    int[][] dp = new int[n][m];
    
    // Initialize first row and first column of dp array
    for (int i = 0; i < n; i++) {
        dp[i][0] = matrix[i][0];
        maxSize = Math.max(maxSize, dp[i][0]);
    }
    for (int j = 0; j < m; j++) {
        dp[0][j] = matrix[0][j];
        maxSize = Math.max(maxSize, dp[0][j]);
    }
    
    // Fill in the rest of the dp array and update maxSize
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (matrix[i][j] == 1) {
                dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                maxSize = Math.max(maxSize, dp[i][j]);
            }
        }
    }
    
    return maxSize * maxSize; // return area of largest square sub-matrix
}

Let’s consider an example to understand the algorithm better. Suppose we have the following binary matrix:

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

We can apply the above algorithm to find the maximum size square sub-matrix with all 1s as follows:

1. Initialize ‘dp[][]‘ and ‘maxSize‘:

dp[][] = 1 0 0 1 1 1
         1 1 1 1 1 1
         0 0 0 0 0 0
         0 0 0 0 0 0
         1 0 0 0 0 0
         0 0 0 0 0 0

maxSize = 1

2. Fill in first row and first column of ‘dp[][]‘:

dp[][] = 1 0 0 1 1 1
         1 1 1 1 1 1
         0 0 0 0 0 0
         0 0 0 0 0 0
         1 0 0 0 0 0
         0 0 0 0 0 0

maxSize = 1

3. Fill in the rest of ‘dp[][]‘ and update ‘maxSize‘:

dp[][] = 1 0 0 1 1 1
         1 1 1 1 1 1
         0 1 1 1 0 0
         0 1 2 2 1 0
         1 2 2 3 2 1
         0 0 1 2 2 0

maxSize = 3

4. Return ‘maxSize * maxSize‘ as the area of the largest square sub-matrix:

maxSize = 3

Area of largest square sub-matrix = maxSize * maxSize = 9

Therefore, the maximum size square sub-matrix with all 1s in the binary matrix is of size 3 x 3 and its area is 9.