Solution Explanation for Counting Square Submatrices with All Ones

This problem asks to count the number of square submatrices within a given matrix that contain only ones. A dynamic programming approach provides an efficient solution.

Approach

The core idea is to build a DP table f where f[i][j] represents the side length of the largest square submatrix with all ones ending at position (i, j).

1. Initialization: If matrix[i][j] == 0, then f[i][j] = 0 because no square can end there. If matrix[i][j] == 1, and i or j is 0 (edge of the matrix), then f[i][j] = 1 as it forms a 1x1 square.

2. Iteration: For any other cell (i, j) where matrix[i][j] == 1, the largest square ending there has a side length of min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1. This is because to extend a square to include the current cell, we need to ensure the cells diagonally above and to the left, and the cell directly above, and the cell directly to the left, all also belong to the square (and thus have the value 1).

3. Counting: The value of f[i][j] directly contributes to the total count of squares. f[i][j] = k means that there are k squares (of sizes 1x1, 2x2, ..., kxk) ending at (i,j).

Time and Space Complexity Analysis

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the input matrix. This is because we iterate through the matrix once to build the DP table.

• Space Complexity: O(m*n) to store the DP table f. We could optimize to O(min(m,n)) space using a rolling array, but that would make the code significantly less readable.

Code Examples (Python and Java)

The following code examples demonstrate the dynamic programming solution in Python and Java. Other languages are similar.

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

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;
    }
}

This detailed explanation, along with the code examples in multiple languages, should provide a comprehensive understanding of the solution to this problem.