__1277. Count Square Submatrices with All Ones__

Given a `m * n`

matrix of ones and zeros, return how many **square** submatrices have all ones.

**Example 1:**

Input:matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ]Output:15Explanation:There are10squares of side 1. There are4squares of side 2. There is1square of side 3. Total number of squares = 10 + 4 + 1 =15.

**Example 2:**

Input:matrix = [ [1,0,1], [1,1,0], [1,1,0] ]Output:7Explanation:There are6squares of side 1. There is1square of side 2. Total number of squares = 6 + 1 =7.

**Constraints:**

`1 <= arr.length <= 300`

`1 <= arr[0].length <= 300`

`0 <= arr[i][j] <= 1`

`Solution:`

Brute Force: We can go to each position and get the maximum size of the square if it is the starting square using some for loops and conditions. But this will be complex. Let's move to dynamic programming.

**Dynamic Programming:**

We can make a matrix of the same size as the input. The first row and the first column of this will be the same size as the input as the size of the square will be 1 if it is 1 or else it will be zero,

Input:

1 | 1 | 1 |

1 | 1 | 1 |

1 | 1 | 1 |

Matrix made by us:

1 | 1 | 1 |

1 | 2 | 2 |

1 | 2 | 3 |

DP state:

if(arr[i][j]==1) dp[i][j]=1+min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});

Why we are taking the minimum of all three is because we need to make a square so the top, left and the previous diagonal should be 1 then only the size of the square will increase.

Now we can find the answer as the sum of all the numbers in the DP and the largest number will be the side of the largest square possible.

Time Complexity: O(N^{2})

Space Complexity: O(N^{2})

## 0 Comments

If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.