# Dynamic Programming – Maximum size square sub-matrix with all 1s

Objective: Given a matrix of 0’s and 1’s (binary matrix). Find out Maximum size square sub-matrix with all 1’s.

Example:

Approach:

Base Cases:

• If only one row is given then cells with 1’s will be the Maximum size square sub-matrix with size = 1.
• If only one column is given then cells with 1’s will be the Maximum size square sub-matrix with size = 1.

Dynamic Programming (Bottom-up).

• Create an auxiliary array of the same size as given input array. We will fill the auxiliary array with Maximum size square sub-matrix with all 1’s possible with respect to the particular cell.
• Once the auxiliary is fill, scan it and find out the maximum entry in it, this will the size of Maximum size square sub-matrix with all 1’s in the given matrix.

How to fill the auxiliary matrix??

• Copy the first row and first column from the given array to auxiliary array. (Read the base cases described earlier).
• For filling rest of cells, check if particular cell’s value is 0 in given array, if yes then put 0 against to that cell in auxiliary array.
• check if particular cell’s value is 1 in given array, if yes then put Minimum (value in the left cell, top cell and left-top diagonal cell) + 1 in auxiliary cell.

Recursive Equation:

```For Given arrA[][], create auxiliary array sub[][].
```

#### Base Cases: sub[i] = arrA[i] i = 0 to row Count // copy the first column sub[i] = arrA[i] i = 0 to column Count // copy the first row

for rest of the cells
sub[i][j] = 0 if arrA[i][j]=0               = Min(arrA[i-1][j], arrA[i][j-1], arrA[i-1][j-1] )
At the End, scan the sub[][] and find out the maximum entry in it.

Example:

Complete Code:

 public class MaxSquareSubMatrix { public void subMatrix(int[][] arrA, int row, int cols) { int[][] sub = new int[row][cols]; // copy the first row for (int i = 0; i < cols; i++) { sub[i] = arrA[i]; } // copy the first column for (int i = 0; i < row; i++) { sub[i] = arrA[i]; } // for rest of the matrix // check if arrA[i][j]==1 for (int i = 1; i < row; i++) { for (int j = 1; j < cols; j++) { if (arrA[i][j] == 1) { sub[i][j] = Math.min(sub[i – 1][j – 1], Math.min(sub[i][j – 1], sub[i – 1][j])) + 1; } else { sub[i][j] = 0; } } } // find the maximum size of sub matrix int maxSize = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < cols; j++) { if (sub[i][j] > maxSize) { maxSize = sub[i][j]; } } } System.out.println("Maximum size square sub-matrix with all 1s: " + maxSize); } public static void main(String[] args) { int[][] arrA = { { 0, 1, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1, 0 }, { 0, 1, 1, 1, 1, 0 }, { 0, 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 1, 1 } }; MaxSquareSubMatrix i = new MaxSquareSubMatrix(); i.subMatrix(arrA, 5, 6); } }

```Output:
Maximum size square sub-matrix with all 1s: 3

```

### 2 thoughts on “Dynamic Programming – Maximum size square sub-matrix with all 1s”

1. Why is it required to go through the matrix sub again to find the maxSize?

Why not keep track of maxSize when sub is being populated?
int maxSize = 0;
for (int i = 1; i < row; i++) {
for (int j = 1; j < cols; j++) {
sub[i][j] = (arrA[i][j] == 0)? 0: Math.min(sub[i – 1][j – 1], Math.min(sub[i][j – 1], sub[i – 1][j])) + 1;
maxSize = Math.max(maxSize, sub[i][j]);
}
}
return maxSize;

• 