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:

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;

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.