# Count Square Submatrices with All Ones
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-square-submatrices-with-all-ones)
Canonical: https://scaleengineer.com/dsa/problems/count-square-submatrices-with-all-ones
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Tinkoff](https://scaleengineer.com/companies/tinkoff)
---
## 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[0].length <= 300`
* `0 <= arr[i][j] <= 1`

# Approaches
## Brute-Force Iteration
The brute-force approach is the most straightforward way to solve the problem. It involves systematically checking every possible submatrix to see if it's a square composed entirely of ones. We can iterate through every cell of the matrix, considering it as the top-left corner of a potential square. From each top-left corner, we then try to form squares of increasing side lengths (1x1, 2x2, 3x3, etc.) and for each size, we verify if all its elements are ones. If they are, we increment our total count.
**Time:** O(m * n * min(m, n)^3). We have loops for rows (m), columns (n), and side length (min(m,n)). Inside, we check an s x s square, which takes O(s^2) time. A slightly better implementation checks only the new border, leading to O(m * n * min(m, n)^2). In either case, it's a high-degree polynomial complexity. · **Space:** O(1) extra space, as we are only using a few variables to keep track of the count and loop indices.
**Pros:** Simple to conceptualize and implement.; Requires no extra space (O(1) space complexity).
**Cons:** Extremely inefficient due to multiple nested loops.; The time complexity makes it infeasible for the given constraints, likely resulting in a 'Time Limit Exceeded' error.
### Explanation
This method iterates through all possible top-left corners `(r, c)` of a square. For each corner, it then iterates through all possible side lengths `s`. For each combination of `(r, c, s)`, it checks if the corresponding `s x s` submatrix contains only ones. A helper function or nested loops can perform this check. If the check passes, a counter is incremented. To add a small optimization, if a square of size `s` starting at `(r, c)` is found to not be all ones, we know that no square of size `s+1` or larger starting at the same corner can be all ones, so we can stop checking for larger sizes from that corner.

```java
class Solution {
    public int countSquares(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int count = 0;

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (matrix[r][c] == 1) {
                    int maxSide = Math.min(m - r, n - c);
                    for (int s = 1; s <= maxSide; s++) {
                        if (isAllOnes(matrix, r, c, s)) {
                            count++;
                        } else {
                            // If a square of size s is not all ones,
                            // no larger square from this corner can be all ones.
                            break;
                        }
                    }
                }
            }
        }
        return count;
    }

    private boolean isAllOnes(int[][] matrix, int r, int c, int s) {
        for (int i = r; i < r + s; i++) {
            for (int j = c; j < c + s; j++) {
                if (matrix[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Get the dimensions of the matrix, `m` (rows) and `n` (columns).
3. Iterate through each cell `(r, c)` from `(0, 0)` to `(m-1, n-1)`. This cell will serve as the potential top-left corner of a square.
4. For each cell `(r, c)`, if `matrix[r][c]` is 1, start checking for squares of increasing size `s` starting from `s=1`.
5. The maximum possible side length `s` for a square starting at `(r, c)` is `min(m-r, n-c)`.
6. For each size `s`, check if the `s x s` submatrix starting at `(r, c)` is composed entirely of ones.
   - This involves a nested loop from `i = r` to `r + s - 1` and `j = c` to `c + s - 1`.
   - If any element `matrix[i][j]` is 0, then it's not a valid square of ones. We can stop checking for larger sizes from this `(r, c)` and break the loop over `s`.
7. If the `s x s` submatrix is all ones, increment the `count`.
8. After all iterations, return the total `count`.

## Dynamic Programming
This approach uses dynamic programming to solve the problem efficiently. The key idea is to build a DP table (let's call it `dp`) of the same size as the input matrix. Each cell `dp[i][j]` will store the side length of the largest square submatrix of all ones whose bottom-right corner is the cell `matrix[i][j]`.

The total number of squares is simply the sum of all values in this `dp` table. This is because a value `k` at `dp[i][j]` implies that there is a `k x k` square ending at `(i, j)`, which also means there are squares of size `(k-1)x(k-1)`, `(k-2)x(k-2)`, ..., `1x1` ending at the same position. Thus, this cell contributes `k` squares to the total count.
**Time:** O(m * n), as we visit each cell of the matrix exactly once to compute its DP value. · **Space:** O(m * n) to store the DP table.
**Pros:** Significantly more efficient time-wise than the brute-force approach.; The logic is a classic and elegant application of dynamic programming.
**Cons:** Requires extra space proportional to the size of the input matrix, which can be significant for large matrices.
### Explanation
We create a `dp` matrix. For any cell `(i, j)`, if `matrix[i][j]` is 0, no square can end there, so `dp[i][j]` is 0. If `matrix[i][j]` is 1, we can form a square of at least size 1. To form a larger square, say of size `k > 1`, we must have a `(k-1)x(k-1)` square ending at `(i-1, j)`, a `(k-1)x(k-1)` square ending at `(i, j-1)`, and a `(k-1)x(k-1)` square ending at `(i-1, j-1)`. The size of the square at `(i, j)` is therefore one plus the minimum of the sizes of these three neighboring squares. We iterate through the matrix, compute each `dp[i][j]`, and add this value to a running total.

```java
class Solution {
    public int countSquares(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], 
                                           Math.min(dp[i - 1][j], dp[i][j - 1]));
                    }
                    count += dp[i][j];
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Get the dimensions of the matrix, `m` and `n`.
3. Create a new 2D array `dp` of size `m x n` to store our results. `dp[i][j]` will store the side length of the largest square of ones with its bottom-right corner at `matrix[i][j]`.
4. Iterate through each cell `(i, j)` of the matrix.
5. If `matrix[i][j]` is 1:
   - If `i` or `j` is 0 (i.e., the cell is in the first row or first column), it can only form a 1x1 square. So, `dp[i][j] = 1`.
   - Otherwise, the size of the square ending at `(i, j)` is limited by the squares ending at its top `(i-1, j)`, left `(i, j-1)`, and top-left `(i-1, j-1)` neighbors. The recurrence relation is `dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`.
6. The value `dp[i][j]` also represents the number of squares that have `(i, j)` as their bottom-right corner. For example, if `dp[i][j] = 3`, it implies there's a 3x3, a 2x2, and a 1x1 square ending at `(i, j)`. So, we add `dp[i][j]` to our total `count`.
7. If `matrix[i][j]` is 0, `dp[i][j]` is 0, and we add nothing to the count.
8. After iterating through all cells, return the total `count`.

## Dynamic Programming with Space Optimization
Observing the recurrence relation `dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`, we can see that to compute the values for the current row `i`, we only need information from the previous row `i-1` and the current row `i` itself. This means we don't need to store the entire `m x n` DP table. We can optimize the space complexity by only keeping track of the DP values for the previous row.
**Time:** O(m * n), as we still iterate through each cell of the matrix once. · **Space:** O(n), where n is the number of columns. We only need to store the DP values for the previous row.
**Pros:** Maintains the optimal O(m*n) time complexity.; Reduces space complexity significantly from O(m*n) to O(n).
**Cons:** The logic can be slightly more complex to manage compared to the standard 2D DP approach, especially when trying to optimize to a single 1D array and a variable.
### Explanation
We can use a 1D array, say `dp`, of size `n` to store the DP values of the row we just processed. When computing the values for the current row, we use this `dp` array for the `dp[i-1]` values. A second array `currentRowDp` can be used to build the results for the current row. After the row is processed, `currentRowDp` becomes the `dp` array for the next iteration. A further optimization can use a single 1D array and a variable `prev` to store the diagonal element `dp[i-1][j-1]`, reducing space to a single `O(n)` array.

```java
class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] dp = new int[n];
        int count = 0;

        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 1) {
                dp[j] = 1;
                count++;
            }
        }

        for (int i = 1; i < m; i++) {
            int prev = dp[0]; // This will be the top-left for the next element (j=1)
            if (matrix[i][0] == 1) {
                dp[0] = 1;
                count++;
            } else {
                dp[0] = 0;
            }
            for (int j = 1; j < n; j++) {
                int temp = dp[j]; // Store the original dp[j] (top neighbor)
                if (matrix[i][j] == 1) {
                    // dp[j] is top, dp[j-1] is left (already updated for current row), prev is top-left
                    dp[j] = 1 + Math.min(prev, Math.min(dp[j], dp[j - 1]));
                    count += dp[j];
                } else {
                    dp[j] = 0;
                }
                prev = temp; // Update prev for the next iteration
            }
        }
        return count;
    }
}
```
### Algorithm
1. Initialize `count = 0`.
2. Get matrix dimensions `m` and `n`.
3. Instead of a 2D DP table, create a 1D array `dp` of size `n`. This array will store the DP values of the previous row.
4. Iterate through the rows of the matrix from `i = 0` to `m-1`.
5. For each row, create a new 1D array `currentRowDp` of size `n` to store the DP values for the current row.
6. Iterate through the columns from `j = 0` to `n-1`.
7. If `matrix[i][j] == 1`:
   - If `i == 0` or `j == 0`, `currentRowDp[j] = 1`.
   - Otherwise, `currentRowDp[j] = 1 + min(dp[j-1], dp[j], currentRowDp[j-1])`.
     - `dp[j-1]` is the top-left neighbor from the previous row's DP values.
     - `dp[j]` is the top neighbor from the previous row's DP values.
     - `currentRowDp[j-1]` is the left neighbor from the current row's DP values.
8. Add `currentRowDp[j]` to the total `count`.
9. After the inner loop (columns) finishes, update the `dp` array for the next iteration: `dp = currentRowDp`.
10. Return `count`.

## Dynamic Programming (In-place)
This is the most space-efficient version of the dynamic programming solution. It reuses the input matrix to store the DP table, thereby eliminating the need for any significant extra space. The logic remains the same as the standard DP approach. The value at `matrix[i][j]` is updated to store the side length of the largest square of ones ending at that cell. This is possible because when we compute the value for `matrix[i][j]`, the original values of its top, left, and top-left neighbors are no longer needed for subsequent calculations; their already-computed DP values are what matter.
**Time:** O(m * n), as we iterate through each cell of the matrix once. · **Space:** O(1) extra space, as all calculations are done in-place on the input matrix.
**Pros:** Optimal time complexity of O(m*n).; Optimal space complexity of O(1) (no extra space besides the input).; Very concise implementation.
**Cons:** This approach modifies the input matrix. If the original matrix needs to be preserved, a copy must be made first, which would negate the space savings and make it equivalent to the standard O(m*n) space DP approach.
### Explanation
We traverse the matrix from top-left to bottom-right. For each cell `(i, j)`, if its value is 1, we update it based on its neighbors. The cells in the first row and first column serve as the base cases; if `matrix[i][j]` is 1, its DP value is 1. For any other cell `(i, j)` where `matrix[i][j]` is 1, we update it to be `1 + min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1])`. The crucial insight is that by the time we process `(i, j)`, the values at `(i-1, j)`, `(i, j-1)`, and `(i-1, j-1)` have already been converted to their final DP values. We sum up these new values as we compute them to get the total count.

```java
class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    if (i > 0 && j > 0) {
                        matrix[i][j] = 1 + Math.min(matrix[i - 1][j - 1], 
                                               Math.min(matrix[i - 1][j], matrix[i][j - 1]));
                    }
                    count += matrix[i][j];
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Get the dimensions of the matrix, `m` and `n`.
3. Iterate through each cell `(i, j)` of the input matrix itself.
4. If `matrix[i][j]` is 1:
   - If the cell is not in the first row or first column (i.e., `i > 0` and `j > 0`):
     - Update the value in the input matrix to store the DP result: `matrix[i][j] = 1 + min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1])`.
   - The value `matrix[i][j]` now represents the side length of the largest square ending at `(i, j)`, which is also the number of squares ending at this cell.
   - Add the current value of `matrix[i][j]` to the total `count`.
5. If `matrix[i][j]` was originally 0, it remains 0 and contributes nothing to the count.
6. After iterating through all cells, return the total `count`.

# Solutions
### Java

```java
class Solution {
public
  int countSquares(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] f = new int[m][n];
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (matrix[i][j] == 0) {
          continue;
        }
        if (i == 0 || j == 0) {
          f[i][j] = 1;
        } else {
          f[i][j] =
              Math.min(f[i - 1][j - 1], Math.min(f[i - 1][j], f[i][j - 1])) + 1;
        }
        ans += f[i][j];
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
function countSquares ( matrix ) { const [ m , n ] = [ matrix . length , matrix [ 0 ]. length ]; const f = Array . from ({ length : m }, () => Array ( n )); const dfs = ( i , j ) => { if ( i === m || j === n || ! matrix [ i ][ j ]) return 0 ; f [ i ][ j ] ??= 1 + Math . min ( dfs ( i + 1 , j ), dfs ( i , j + 1 ), dfs ( i + 1 , j + 1 )); return f [ i ][ j ]; }; let ans = 0 ; for ( let i = 0 ; i < m ; i ++ ) { for ( let j = 0 ; j < n ; j ++ ) { ans += dfs ( i , j ); } } return ans ; }
```

### CPP

```cpp
class Solution {
public:
  int countSquares(vector<vector<int>> &matrix) {
    int m = matrix.size(), n = matrix[0].size();
    int ans = 0;
    vector<vector<int>> f(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (matrix[i][j] == 0)
          continue;
        if (i == 0 || j == 0)
          f[i][j] = 1;
        else
          f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
        ans += f[i][j];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int: m, n = len(matrix), len(matrix[0]) f = [[0] * n for _ in range(m)] ans = 0 for i, row in enumerate(matrix): for j, v in enumerate(row): if v == 0: continue if i == 0 or j == 0: f[i][j] = 1 else: f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1 ans += f[i][j] return ans

```