Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have explored various ways to solve the problem of finding maximum size square submatrix with all 1s. This can be solved using Dynamic Programming.

Table of Contents |
---|

1) Introduction |

2) Naive approach |

3) Recursive approach |

4) Dynamic Programming approach |

5) Conclusion |

Pre-requisites:

- Complete list of Dynamic Programming problems

## 1) Introduction

*Given an m×n binary matrix.Find the size of largest square submatrix with all ones.*

A binary matrix is that which consists of only 0s and 1s.

Let's understand the problem statement through a figure.

In the above matrix the submatrix with color 'yellow' is of size 2×2 and the submatrix with color 'red' is of size 3×3.

Hence, the largest square submatrix with all ones is of size 3 in the above case.

## 2) Naive approach

In this approach if a cell's value is 1,we incrementally check what can be the largest square submatrix(1×1 or 2×2 or 3×3....) with all ones exist considering each cell as the top-left corner of square submatrix.

Consider the following matrix

Considering cell colored with 'blue' as top-left corner top-left corner of square submatrix.

The algorithm works in the following way

It checks whether a 1×1 submatrix then a 2×2 submatrix then a 3×3 submatrix and so on can be formed.

**STEPS:**

- Go to each cell of the matrix
- If the cell has 1, then find the largest square of 1s with the current cell as the top left corner.

2.1. Simply traverse the cells incrementally one by one till a 0 is encountered

2.2. Increase size of square to be checked and check newly added cells. - Keep track of the size of the largest square.

`def maxSizeSquareSubMatrixWithAllOnes(matrix): rows,cols=len(matrix),len(matrix[0]) res=0#store the maximum size of submatrix with all ones for i in range(rows): for j in range(cols): #initializing to next row and column to check #feasibility of submatrix as discussed rowCheck,colCheck=i+1,j+1 #flag variable is used to stop checking #incase a zero is found flag=True while rowCheck<rows and colCheck<cols and flag: #check for the next possible submatrix last column #contains all ones or not for row in range(i,rowCheck+1): if matrix[row][colCheck]==0: flag=False#if any of the cell is 0 we can't proceed break #check for the next possible submatrix last row #contains all ones or not for col in range(j,colCheck+1): if matrix[rowCheck][col]==0: flag=False#if any of the cell is 0 we can't proceed break if flag:#if we find a feasible submatrix res=max(res,rowCheck-i+1)#update #increment to check next possible submatrix size rowCheck+=1 colCheck+=1 return resprint(maxSizeSquareSubMatrixWithAllOnes(matrix = [ [1,1,0,1,0,0], [1,1,1,1,1,1], [1,0,1,1,1,0], [0,0,1,1,1,0],]))`

Output:

`3`

**Time complexity:**

To visit each cell in the matrix it takes **O(m×n)** time complexity.

To calculate largest square submatrix with all ones we consider each cell as the top-left corner of a submatrix and check for the maximum size submatrix possible incrementally i.e.,1×1 , 2×2 , 3×3 and so on.This takes **O(m×n)** time complexity.

Hence overall it takes **O(mn)×O(mn)=O((mn) ^{2})** , where

**m**and

**n**are the number of rows and columns of the given matrix respectively.

## 3) Recursive approach

This approach is similar to the above one but solving the method recursively.

**STEPS:**

- Go to each cell of the matrix
- If the cell has 1, then find the largest square of 1s with the current cell as the top left corner.

2.1. Recursively traverse the cells to find the largest square of 1s till a 0 is encountered or position is not valid. - Keep track of the size of the largest square.

`def maxSizeSquareSubMatrixWithAllOnes(matrix): rows,cols=len(matrix),len(matrix[0]) res=0 #function to check if a given position is valid def isValidPos(i,j): if i<0 or j<0 or i>=rows or j>=cols: return False return True def helper(i,j): if isValidPos(i,j)==False or matrix[i][j]==0:#if the position is not valid or the cell value is 0 nothing can be built from it return 0 return 1+min(helper(i+1,j+1),min(helper(i+1,j),helper(i,j+1)))#recurrence relation for i in range(rows): for j in range(cols): res=max(res,helper(i,j))#for each cell in the matrix calculate the largest square submatrix with all ones with it as the top-left corner return resprint(maxSizeSquareSubMatrixWithAllOnes(matrix = [ [1,1,0,1,0,0], [1,1,1,1,1,1], [1,0,1,1,1,0], [0,0,1,1,1,0],]))`

Output:

`3`

**Time complexity:**

To visit each cell in the matrix it takes **O(m×n)** time complexity.

For each cell calculate the matrix is traversed again recursively in three directions taking **O(3 ^{(m+n)})** time complexity.

Hence overall it takes

**O(m×n×3**, where m and n are the number of rows and columns of the given matrix respectively.

^{(m+n)})There'll be space overhead considering the recursion stack.

Consider the pictorial representation of recursion calls

There are overlapping subproblems and also there is optimal substructure.Hence, the problem can be solved using Dynamic Programming.

## 4) Dynamic Programming approach

Here we'll consider each cell in the dp table as the bottom-right corner of a square submatrix.

Consider a 2×2 matrix, it is said to contain all ones if the bottom-right corner is 1 along with each of top, left, and top-left cells are all 1s.

Consider a 3×3 matrix, it is said to contain all ones if the bottom-right corner is 1 along with each of top, left, and top-left all are bottom-right corners of some 2×2 sub-matrix.

In general for any n×n matrix is said to contain all ones if the bottom-right corner is 1 along with each of top, left, and top-left all are bottom-right corners of some (n-1)×(n-1) sub-matrix.

In dp approach if the current cell is 1 we look for surrounding cells to know whether the size of the matrix can be increased or not.

The surrounding cells here are the top cell, the left cell and the top-left cell.

If all the surrounding cells are 1s then the size of square submatrix can be increased.

If any of the surrounding cells is 0 then the size of square submatrix does not get increased.

We store the maximum square submatrix size with bottom-right corner as given position (i,j) in the matrix in the dp table so that the values can be used for further computation.

**DP Structure:**

**dp[i][j]=Size of largest square submatrix with all 1s having bottom-right corner as (i,j). **

**Base Case:**

The first row and first column values of the dp table are copied as it from the matrix because if a cell is zero then it won't form any sub-matrix and even it is 1 the size of largest square sub-matrix ending with it is still 1.

**If i=0 or j=0 dp[i][j]=matrix[i][j] **

**DP equation:**

**If matrix[i][j]=0 dp[i][j]=0Else dp[i][j]=1+min(dp[i][j-1],dp[i-1][j-1],dp[i-1][j]) **

Let's take an example and build up the dp table

Consider the matrix

Building the dp table..

Fill the first row and column as it is from the matrix.

In the resultant dp matrix above the maximum value is 2.Hence, the maximum square sub-matrix with all 1s in the matrix is 2×2.

**STEPS:**

- Let given matrix be

with**mat**

rows and**m**

columns.**n** - Create a

matrix with size that of**dp**

i.e.,**mat**

.**m×n** - Initialize the

matrix with**dp**

.**zeros** - Start traversing the

matrix**dp**

4.1. if the current cell

belongs to first row**(i,j)**

or first column**(i=0)**

then its value will same as that of in**(j=0)**

i.e.,**mat**

.**dp[i][j]=mat[i][j]**

4.2. If the current cell

has value 0 in**(i,j)**

then its value will be 0 in**mat**

too i.e.,**dp**

.**dp[i][j]=0**

4.3. If the current cell

has value 1 in**(i,j)**

then its value in**mat**

will be one plus minimum of the**dp**

values of current cell's top,left,top-left cells i.e.,**dp**

.**dp[i][j]=1+min(dp[i][j-1],dp[i-1][j-1],dp[i-1][j])** - Keep track of the size of the largest square.

### DP Implementation

`def maxSizeSquareSubMatrixWithAllOnes(matrix): rows,cols=len(matrix),len(matrix[0]) res=0 dp=[[0 for j in range(cols)] for i in range(rows)]#initialize dp matrix with 0s for i in range(rows): for j in range(cols): if i==0 or j==0: dp[i][j]=matrix[i][j]#copying the first row and column as it is(Base Case) else: if matrix[i][j]==0: dp[i][j]=0#if a cell is 0 then no submatrix can be formed using it else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j-1],dp[i-1][j])#dp equation(recur) res=max(res,dp[i][j])#update the maximum size each time return resprint(maxSizeSquareSubMatrixWithAllOnes(matrix = [ [1,1,0,1,0,0], [1,1,1,1,1,1], [1,0,1,1,1,0], [0,0,1,1,1,0],]))`

`3`

## 5) Conclusion

Hence,for the given problem dynamic programming approach is the optimized one with time complexity of **O(m×n)** since the given matrix is traversed once and space complexity of **O(m×n)** since a dp matrix is used, where **m** and **n** are the number of rows and columns of the given matrix respectively.

With this article at OpenGenus, you must have the complete idea of solving the problem "Maximum size square submatrix with all 1s".