Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Count Square Submatrices with All Ones
Bookmark
Input
Example 1
Example 2
Example 3
Custom
matrix
=
[[0,1,1,1],[1,1,1,1],[0,1,1,1]]
3x4
count =
0
0
1
1
1
1
1
1
1
0
1
1
1
each 1 counts the squares ending at it; the answer is the sum
3x4
count =
0
0
1
1
1
1
1
1
1
0
1
1
1
each 1 counts the squares ending at it; the answer is the sum
3x4
count =
0
0
1
1
1
1
1
1
1
0
1
1
1
i = 0
j = 0
matrix[0][0] = 0
no square ends on a 0
3x4
count =
2
+1
0
1
1
1
1
1
1
1
0
1
1
1
i = 0
j = 2
edge cell:
1
square (1x1) ends here, count + 1 =
2
3x4
count =
3
+1
0
1
1
1
1
1
1
1
0
1
1
1
i = 0
j = 3
edge cell:
1
square (1x1) ends here, count + 1 =
3
3x4
count =
4
+1
0
1
1
1
1
1
1
1
0
1
1
1
i = 1
j = 0
edge cell:
1
square (1x1) ends here, count + 1 =
4
3x4
count =
7
+2
0
1
1
1
1
1
2
1
0
1
1
1
i = 1
j = 2
min(
1
,
1
,
1
) + 1 =
2
2 squares end here
3x4
count =
9
0
1
1
1
1
1
2
2
0
1
1
1
i = 2
row 2
stamp each 1 with the squares it ends
3x4
count =
9
0
1
1
1
1
1
2
2
0
1
1
1
i = 2
j = 0
matrix[2][0] = 0
no square ends on a 0
3x4
count =
12
+2
0
1
1
1
1
1
2
2
0
1
2
1
i = 2
j = 2
min(
2
,
1
,
1
) + 1 =
2
2 squares end here
3x4
count =
15
0
1
1
1
1
1
2
2
0
1
2
3
15
squares = 10 (1x1) + 4 (2x2) + 1 (3x3)
algo
master
.
io
Step:
Count every all-1s square. Each 1 answers: how many squares END at me? Sum the answers
0 / 16
Input
Example 1
Example 2
Example 3
Custom
matrix
=
[[0,1,1,1],[1,1,1,1],[0,1,1,1]]
0 / 16
algo
master
.
io
Step:
Count every all-1s square. Each 1 answers: how many squares END at me? Sum the answers
