# 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][0] = arrA[i][0] i = 0 to row Count // copy the first column

sub[0][i] = arrA[0][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:**

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

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;

Yes we can do that as well. nice approach.