Count Square Submatrices With All Ones - Leetcode Solution

Problem Statement: Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example: 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.

Solution: The idea of the solution is to create an auxiliary matrix count[][] such that count[i][j] represents the size of the biggest square sub-matrix with all 1s including matrix[i][j] as its bottom-right corner.

Let’s consider the matrix in the example matrix = [[0, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]].

count[0][0] = 0 because matrix[0][0] = 0 count[0][1] = 1 because matrix[0][1] = 1 count[0][2] = 1 because matrix[0][2] = 1 count[0][3] = 1 because matrix[0][3] = 1 count[1][0] = 1 because matrix[1][0] = 1 count[1][1] = 2 because matrix[1][1] = 1, and it creates a square of size 2x2 count[1][2] = 2 because matrix[1][2] = 1, and it creates a square of size 2x2 count[1][3] = 2 because matrix[1][3] = 1, and it creates a square of size 2x2 count[2][0] = 0 because matrix[2][0] = 0 count[2][1] = 1 because matrix[2][1] = 1 count[2][2] = 2 because matrix[2][2] = 1, and it creates a square of size 2x2 count[2][3] = 3 because matrix[2][3] = 1, and it creates a square of size 3x3

The final answer will be a summation of all values in the matrix count[][].

Algorithm:

1. Create a variable count to store the number of squares. Initialize it to 0.
2. Create a 2D matrix count of size (m+1)x(n+1) and initialize all the cells with 0.
3. Traverse through the matrix from the second row and second column. a. If the current element in the matrix is 1, then set count[i][j] to the minimum of count[i-1][j], count[i][j-1], and count[i-1][j-1] + 1. b. Keep updating the count variable with the value of count[i][j].
4. Return the value of count.

Code:

class Solution: def countSquares(self, matrix: List[List[int]]) -> int: m, n = len(matrix), len(matrix[0]) count = 0

    # Create a matrix of size(m+1)x(n+1)
    # Initialize all the cells with 0
    count_matrix = [[0 for _ in range(n+1)] for _ in range(m+1)]
    
    # Traverse through the matrix
    for i in range(1, m+1):
        for j in range(1, n+1):
            if matrix[i-1][j-1] == 1:
                # Update the value of count_matrix[i][j]
                count_matrix[i][j] = min(count_matrix[i-1][j], count_matrix[i][j-1], count_matrix[i-1][j-1]) + 1
            
            # Update the count variable with the value of count_matrix[i][j]
            count += count_matrix[i][j]
            
    return count

Time complexity: O(mn) Space complexity: O(mn)

1