Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Count Square Submatrices with All Ones
Bookmark
Brute Force
2D DP
Space Optimized
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 =
1
+1
0
1
1
1
1
1
1
1
0
1
1
1
i = 0
j = 1
edge cell:
1
square (1x1) ends here, count + 1 =
1
3x4
count =
3
0
3
1
1
1
1
1
1
0
1
1
1
i = 0
j = 2
3x4
count =
5
0
3
2
1
1
1
1
1
0
1
1
1
i = 0
j = 3
3x4
count =
7
0
3
2
1
1
1
1
1
0
1
1
1
i = 1
j = 0
3x4
count =
8
0
3
2
1
1
1
1
1
0
1
1
1
i = 1
j = 1
3x4
count =
10
0
3
2
1
1
2
1
1
0
1
1
1
i = 1
j = 2
3x4
count =
12
0
3
2
1
1
2
2
1
0
1
1
1
i = 2
j = 0
matrix[2][0] = 0
no square ends on a 0
3x4
count =
13
0
3
2
1
1
2
2
1
0
1
1
1
i = 2
j = 2
3x4
count =
15
0
3
2
1
1
2
2
1
0
1
1
1
15
squares = 10 (1x1) + 4 (2x2) + 1 (3x3)
algo
master
.
io
Step:
Count every all-1s square. Anchor a square at each 1 and grow it while every cell stays a 1
0 / 76
Input
Example 1
Example 2
Example 3
Custom
matrix
=
[[0,1,1,1],[1,1,1,1],[0,1,1,1]]
0 / 76
algo
master
.
io
Step:
Count every all-1s square. Anchor a square at each 1 and grow it while every cell stays a 1
