**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:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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[0][i] = arrA[0][i]; | |

} | |

// copy the first column | |

for (int i = 0; i < row; i++) { | |

sub[i][0] = arrA[i][0]; | |

} | |

// 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