Medium

Count Square Submatrices with All Ones

LAB

Given a binary matrix, count all square submatrices that contain only ones.

EXAMPLES

Example 1

Input
{
  "matrix": [
    [
      0,
      1,
      1,
      1
    ],
    [
      1,
      1,
      1,
      1
    ],
    [
      0,
      1,
      1,
      1
    ]
  ]
}

Output
15

FUNCTION SHAPE

matrix: intMatrix→int

SOLUTION NOTE

This reuses the Maximal Square recurrence. Instead of only taking the maximum side length, sum dp(i,j) because each top-left cell contributes one square of every size up to that side length.

Reveal reference solution +

pythonREFERENCE

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

    @cache
    def dp(i, j):
        if i >= m or j >= n or matrix[i][j] == 0:
            return 0
        return 1 + min(dp(i + 1, j), dp(i, j + 1), dp(i + 1, j + 1))

    return sum(dp(i, j) for i in range(m) for j in range(n))

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗