Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

If the largest all-ones square ending at a cell has side length s, that cell is also the bottom-right corner of one square of each size from one through s. A larger square needs compatible squares directly above, left, and diagonally above-left; its size is limited by the smallest of those three.

Approach

Process cells row by row, reusing the matrix as the DP table. Leave zero cells unchanged. For a one away from the top and left edges, replace it with one plus the minimum of its three already-computed neighbors; boundary ones remain one. Add each resulting value to the total. Every square is counted once at its unique bottom-right corner.

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

        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 1:
                    if i > 0 and j > 0:
                        matrix[i][j] += min(matrix[i][j - 1], matrix[i - 1][j - 1], matrix[i - 1][j])
                    res += matrix[i][j]
        
        return res

Complexity analysis

For an R × C matrix, the in-place DP visits each cell once, so time is O(RC) and auxiliary space is O(1).