Array Matrix Breadth First Search
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) = 3
cols (int) = 3
Return:
(int) 7
Example 2
Input:
matrix (int[][]) = [[1,1],[1,1]]
rows (int) = 2
cols (int) = 2
Return:
(int) 5
Example 3
Input:
matrix (int[][]) = [[0,0],[0,0]]
rows (int) = 2
cols (int) = 2
Return:
(int) 0

Use 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 count
Run your code to see the result.