Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given a matrix of 0’s and 1’s (binary matrix). Find out Max­i­mum size square sub-matrix with all 1’s.

Exam­ple:

Maximum size square sub-matrix with all 1s Example

Max­i­mum 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 Max­i­mum size square sub-matrix with size = 1.
  • If only one col­umn is given then cells with 1’s will be the Max­i­mum size square sub-matrix with size = 1.

Dynamic Pro­gram­ming (Bottom-up).

  • Cre­ate an aux­il­iary array of the same size as given input array. We will fill the aux­il­iary array with Max­i­mum size square sub-matrix with all 1’s pos­si­ble with respect to the par­tic­u­lar cell.
  • Once the aux­il­iary is fill, scan it and find out the max­i­mum entry in it, this will the size of Max­i­mum size square sub-matrix with all 1’s in the given matrix.

How to fill the aux­il­iary matrix??

  • Copy the first row and first col­umn from the given array to aux­il­iary array. (Read the base cases described earlier).
  • For fill­ing rest of cells, check if par­tic­u­lar cell’s value is 0 in given array, if yes then put 0 against to that cell in aux­il­iary array.
  • check if par­tic­u­lar cell’s value is 1 in given array, if yes then put Min­i­mum (value in the left cell, top cell and left-top diag­o­nal cell) + 1 in aux­il­iary cell.

Recur­sive Equation:

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

Base Cases:
sub[i][0] = arrA[i][0] i = 0 to row Count // copy the first col­umn
sub[0][i] = arrA[0][i] i = 0 to col­umn 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 max­i­mum entry in it.

Exam­ple:

Maximum size square sub-matrix - Auxiliary Array

Max­i­mum size square sub-matrix — Aux­il­iary Array

Com­plete Code:

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

You may also like...

  • Mithun Mathew

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

    Why not keep track of max­Size when sub is being pop­u­lated?
    int max­Size = 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;
    max­Size = Math.max(maxSize, sub[i][j]);
    }
    }
    return maxSize;

    • tuto­ri­al­hori­zon

      Yes we can do that as well. nice approach.