We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Square Submatrices with All Ones

Difficulty: Medium

Problem Description

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

Key Insights

  • A square submatrix is defined by its top-left corner and its size.
  • The number of square submatrices that can be formed depends on the minimum size of square submatrices that can be formed at each position in the matrix.
  • Dynamic programming can be used to keep track of the size of the largest square submatrix that can end at each position.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

To solve the problem, we can use a dynamic programming approach. We will maintain a DP table where each entry dp[i][j] represents the size of the largest square submatrix that has its bottom-right corner at position (i, j).

  1. Initialize a DP table of the same size as the input matrix, filled with zeros.
  2. Iterate through each cell in the matrix:
    • If the cell contains a 1, update dp[i][j] to be the minimum of the values from the left, top, and top-left diagonal cells plus one.
    • If the cell contains a 0, then dp[i][j] remains 0.
  3. The value in dp[i][j] will give the size of the largest square that can be formed at that position, and we can accumulate these values to get the total count of all square submatrices.

Code Solutions

def countSquares(matrix):
    if not matrix:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    count = 0
    
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                count += dp[i][j]
    
    return count
← Back to All Questions