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:

Maximum size square sub-matrix with all 1s Example
Maximum size square sub-matrix with all 1s 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:

Maximum size square sub-matrix - Auxiliary Array
Maximum size square sub-matrix – Auxiliary Array

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