mediumDynamic Programming 2DPure DSA~30 min
Count All All-Ones Square Submatrices
In a binary occupancy grid, count every solid square block of any size — a tally used to score dense regions.
Problem
Given an m x n binary matrix, return the total number of square submatrices that are entirely filled with 1s, counting squares of every size.
Input
An m x n binary matrix.
Output
An integer: the total count of all-ones square submatrices.
Constraints
- 1 <= m, n <= 300
- matrix[i][j] is 0 or 1.
Examples
Example 1
Input
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
Output
15
10 unit squares + 4 of size 2 + 1 of size 3 (counting overlapping) = 15.
Example 2
Input
matrix = [[1,0,1],[1,1,0],[1,1,0]]
Output
7
Six 1x1 squares plus one 2x2 square.