Problems/209. Count Square Submatrices
PrevNext

209. Count Square Submatrices

MediumMatrix

Given an m x n binary grid of 0s and 1s, count the total number of square subgrids composed entirely of 1s.

Example 1
Input: grid = [ [0, 1, 1], [1, 1, 1], [0, 1, 1] ]
Output: 7
There are 6 squares of size 1x1, and 1 square of size 2x2. The total sum is 6 + 1 = 7.
Example 2
Input: grid = [ [1, 0, 1], [1, 1, 0], [1, 1, 0] ]
Output: 6
There are 5 squares of size 1x1, and 1 square of size 2x2 ending at (2,1), yielding a total of 6.
Example 3
Input: grid = [ [0] ]
Output: 0
No 1s exist in the grid, so the count is 0.
Visualizer
⌥

Visualizer will appear here