Count Square Submatrices of Ones
Intermediate
matrix holds 0s and 1s. Return the number of square submatrices (of any size) that contain only 1s.
For [[0, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]] the answer is 15.
Examples
Example 1
Input:
count_squares([[0, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]])
Output:
15
Example 2
Input:
count_squares([[1, 0, 1], [1, 1, 0], [1, 1, 0]])
Output:
7
Constraints
0 <= rows, cols <= 500- Every cell is
0or1.
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programminggrid-dp
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.