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.
Constraints:
1 <= arr.length <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1
Idea:
Dynamic Programing
- dp[i][j] := edge of largest square with bottom right corner at (i, j)
- base case:
- dp[0][0], dp[i][0], dp[0][j] = 1 if martix[i][j] = 1
- The current unit can form the largest square matrix with the left, upper and upper left units. For example, a unit can form a matrix with a side length of 3 with the left, top, and top left units. That can also form a matrix with a side length of 2 and a side length of 1. So:
- dp[i][j] = min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1])+1 if matrix[i][j] == 1 else 0
- Return answer:
- ans = sum of all dp[i][j]
Solution:
/**
* @param {number[][]} matrix
* @return {number}
*/
var countSquares = function(matrix) {
let row = matrix.length;
let col = matrix[0].length;
let dp = Array.from(new Array(row), () => new Array(col));
let sum = 0;
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
// Basic cases:
// dp[0][0], dp[i][0], dp[0][j] cases => has 1, form a square
dp[i][j] = matrix[i][j];
if (i && j && dp[i][j]) // Why? See Above
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;
sum += dp[i][j];
}
}
return sum;
};