This post is completed by 3 users

  • 1
Add to List
Medium

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

Objective: Given a matrix of 0's and 1's (binary matrix). Find out the 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:

  1. If only one row is given then cells with 1's will be the Maximum size square sub-matrix with size = 1.
  2. 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).

  1. Create an auxiliary array of the same size as the 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.
  2. Once the auxiliary is filled, scan it and find out the maximum entry in it, this will be the size of the Maximum size square sub-matrix with all 1's in the given matrix.

How to fill the auxiliary matrix??

  1. Copy the first row and first column from the given array to the auxiliary array. (Read the base cases described earlier).
  2. For filling the rest of the cells, check if a particular cell's value is 0 in the given array, if yes then put 0 against that cell in the auxiliary array.
  3. check if a particular cell's value is 1 in the given array, if yes then put Minimum (value in the left cell, top cell, and left-top diagonal cell) + 1 in the 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

Output:

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