# LeetCode “Count Square Submatrices with All Ones” Problem Solution

## Problem:

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:

15

Explanation:

There are 10 squares of side 1.

There are 4 squares of side 2.

There is 1 square 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:

7

Explanation:

There are 6 squares of side 1.

There is 1 square of side 2.

Total number of squares = 6 + 1 = 7.

Constraints:

• `1 <= arr.length <= 300`
• `1 <= arr.length <= 300`
• `0 <= arr[i][j] <= 1`

## Solution:

For this problem solution, we will use Dynamic Programming, as you can see from the following drawing we have Overlapping Subproblems with Optimal Substructure which together form the perfect characteristic of any Dynamic Programming problem.

`cache[i][j]` represent the length of the biggest square whose lower-right corner element is `matrix[i][j]`.  Also, there are `cache[i][j]` squares whose lower-right corner element are `matrix[i][j]`.

As Figure, the square edge length ( whose lower-right corner element is `matrix[i][j]` ) is not greater than `the minium of three items (top, above, diagonal) + 1`. And when `matrix[i][j]==0``cache[i][j]=0`. LeetCode Count Square Submatrices with All One’s simulation

## Code:

```public class CountSquareSubmatricesWithAllOnes {
public int countSquares(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}

int result = 0;
int[][] cache = new int[matrix.length][matrix.length];

// initialize first column of the cache object
for(int i = 0; i < matrix.length; i++){
cache[i] = matrix[i];
result += cache[i];
}

// initialize first row of the cache object
for(int i = 1; i < matrix.length; i++){
cache[i] = matrix[i];
result += cache[i];
}

for(int i = 1; i < matrix.length; i++){
for(int j = 1; j < matrix.length; j++){
if(matrix[i][j] == 1){
cache[i][j] = Math.min(Math.min(cache[i - 1][j-1], cache[i - 1][j]), cache[i][j-1]) + 1;
result += cache[i][j];
}
}
}

return result;
}

public static void main(String[] args) {
int[][] matrix = new int[][]{
{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 1, 1, 1}
};
CountSquareSubmatricesWithAllOnes cs = new CountSquareSubmatricesWithAllOnes();
assert cs.countSquares(matrix) == 15;
}
}
```

• Time: O(nm)
• Space: O(nm)