LeetCode: 1277. Count Square Submatrices with All Ones

Dynamic Programming / Medium

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Solution

function ones(matrix, r, c, d) {
    if (r+d >= matrix.length || c+d >= matrix[0].length) {
        return 0;
    }
    for (let i=0; i<=d; i++) {
        if (matrix[r+d][c+i] == 0) {
            return 0;
        }
        if (matrix[r+i][c+d] == 0) {
            return 0;
        }
    }
    
    return 1 + ones(matrix, r,c, d+1);
}
function countSquares(matrix) {
    let sum = 0;
    for (let r=0; r<matrix.length; r++) {
        for (let c=0; c<matrix[0].length; c++) {
            sum += ones(matrix, r, c, 0);
        }
    }
    return sum;
};