Count Square Submatrices with All Ones

Problem Id: 1277 Difficulty: Medium Tag: Array Tag: Dynamic Programming


Intuition

The solution is really intuitive, with Dynamic Programming.

Once a m * m matrix has all ones, the (m - 1) * (m - 1) matrix on its up left corner should be an matrix with all ones.

So for each point, we can easily calculate how many matrix with all ones are there whose left up corner are this point.

Solution


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        count = 0
        rows, cols = len(matrix), len(matrix[0])
        for i in range(rows):
            for j in range(cols):
                ei, ej = i, j
                full = True
                while full and ei < rows and ej < cols:
                    for p in range(i, ei + 1):
                        full = full and matrix[p][ej]
                    for q in range(j, ej + 1):
                        full = full and matrix[ei][q]
                    if full:
                        count += 1
                    ei += 1
                    ej += 1
        return count