Count Square Submatrices with All Ones
You are given a binary matrix matrix containing only 0s and 1s.
Your task is to find the total number of square submatrices that contain only 1s.
A square submatrix can have any valid size, such as 1 × 1, 2 × 2, 3 × 3, and so on. Each square is counted separately based on its position in the matrix.
Return the total number of such square submatrices.
Example 1:
Input: matrix = [ [1, 1, 1], [1, 1, 1], [0, 1, 1] ]
Output: 11
Explanation:
There are:
- 8 squares of size 1 × 1
- 3 squares of size 2 × 2
- 0 squares of size 3 × 3
Therefore: 8+3 =11
Example 2:
Input: matrix = [ [1, 0, 1, 1], [1, 1, 1, 1], [1, 1, 1, 0] ]
Output: 13
Explanation:
There are 10 individual 1 × 1 squares.
There is also 3 square of size 2 × 2.
So total count is 13.
Now Your Turn!
Pick the correct output for the given inputInput: matrix = [ [1, 1], [1, 1]]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= matrix.length <= 300
- 1 <= matrix[0].length <= 300
- 0 <= matrix[i][j] <= 1