LC-1277 Medium LeetCode

1277. Count Square Submatrices with All Ones

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 79% Topics: Array, Dynamic Programming, Matrix

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Math & Geometry 12 min

Reference solution (spoiler · python)

# Time:  O(m * n)
# Space: O(1)

class Solution(object):
    def countSquares(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        for i in xrange(1, len(matrix)):
            for j in xrange(1, len(matrix[0])):
                if not matrix[i][j]:
                    continue
                l = min(matrix[i-1][j], matrix[i][j-1])
                matrix[i][j] = l+1 if matrix[i-l][j-l] else l
        return sum(x for row in matrix for x in row)

Solution from kamyu104/LeetCode-Solutions · MIT