Leetcode Daily Question 27/10/2024 - 1277. Count Square Submatrices with All Ones

Problem Description:

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

from typing import List
class Solution:
  def countSquares(self, matrix: List[List[int]]) -> int:
    if not matrix:
      return 0
    count = 0
    m = len(matrix)
    n = len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    
    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

Explanation:

We can solve this using dp. The idea is to store the amount of squares with all ones ending in the position (i, j) in the matrix.

We traverse the matrix cell by cell and check if the current cell is a 1. If it is not, we ignore and continue. If it is, then we can check the previous neighbours to see what the maximum achievable all-ones squares are.

Since we are only interested in square submatrix, it is enough to check the neighbour one cell up, one cell left, and one cell diagonally left and up.

Summing up all the these states will give us the count in the end.

def countSquares(self, matrix: List[List[int]]) -> int:
    if not matrix:
      return 0
    count = 0
    m = len(matrix)
    n = len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    
    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

The time complexity is O(m * n). This is because we need to traverse cell by cell once to solve the subproblems and do the count.

The space complexity is O(m * n). This is because we need to store the information of number of all-ones squares ending in cell (i, j).

The full solution can be found near the top of the page.