#1277
Count Square Submatrices with All Ones
pupil · 425 · lc medium +25 · verified · 80.7% accepted · 5,941 likes · top 92%
Description
You are given a m x n binary matrix. Count the total number of square submatrices in which every cell contains 1. Return that count.
Example 1:
Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input: matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
Output: 7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.
Code
1
2
3