Count square submatrices with all ones

Given a binary matrix, return the total number of square submatrices that contain only 1s.

matrix dynamic-programming counting

Write a function `count_squares(matrix)` that takes a non-empty 2D list of integers (each element is 0 or 1) representing a binary matrix and returns the total number of square submatrices that consist entirely of 1s. A square submatrix is any contiguous square region of the matrix, including 1x1 cells. The result can be large; return it as an integer.

Constraints

- `1 <= len(matrix)`, `1 <= len(matrix[0])`
- Each element is either 0 or 1.
- The matrix may be rectangular (rows can differ from columns).
- Complexity target: O(rows * cols) time and O(cols) extra space (or O(rows*cols) space acceptable).

Example

>>> count_squares([[1,0,1],[1,1,0],[1,1,0]])
7
>>> count_squares([[0,0,0],[0,0,0]])
0
>>> count_squares([[1]])
1

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of dynamic programming where dp[i][j] represents the size of the largest square ending at cell (i,j).

How many squares end at a cell? Exactly dp[i][j] if that cell is the bottom-right corner.

Transition: if matrix[i][j]==1, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

Sum all dp values to get the total count.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.