Intermediate Level
Implement the countSquareSubmatricesOnes method that counts square submatrices that contain only 1 values.
The input matrix matrix contains only 0 and 1 values, along with its rows and cols.
Your task is to count how many square submatrices are made completely of 1s. Squares of all valid sizes must be counted.
For example, a 2 × 2 matrix filled with 1s contains four 1 × 1 squares and one 2 × 2 square, so the answer is 5.
Example 1
Input
matrix (int[][]) =
[[1,0,1],[1,1,0],[1,1,0]]rows (int) =
3cols (int) =
3Returns (int)
7Example 2
Input
matrix (int[][]) =
[[1,1],[1,1]]rows (int) =
2cols (int) =
2Returns (int)
5Example 3
Input
matrix (int[][]) =
[[0,0],[0,0]]rows (int) =
2cols (int) =
2Returns (int)
0Use dynamic programming to count how many squares end at each cell.
If a cell contains 0, it contributes nothing. If it contains 1, the number of square sizes ending at that cell is 1 + minimum(top, left, diagonal).
Add each calculated value to the answer because a value of 3 means this cell completes three squares: 1 × 1, 2 × 2, and 3 × 3.
Pseudocode:
function countSquareSubmatricesOnes(matrix, rows, cols):
create dp matrix filled with 0
count = 0
for i from 0 to rows - 1:
for j from 0 to cols - 1:
if matrix[i][j] == 1:
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
count = count + dp[i][j]
return countReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run