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.
The trick here is to find how many squares can be formed at matrix[i][j]
From the image you can say that
matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1
In words it's the minimum of top, left and diagonal and the current square so add 1
You can solve this by recursion and checking matrix[i][j] can make a square, but it will be O(n^3)
To optimize we can use above technique, which is basically dynamic programming
Algorithm:
- Initialize a result matrix to add up square matrices as encountered
- Loop through each element matrix[i][j] and check the maximum square can be formed at that point
- Add matrix[i][j] to res
Here's the code:
/**
* @param {number[][]} matrix
* @return {number}
*/
var countSquares = function(matrix) {
let res = 0
for(let i = 0; i < matrix.length; i++) {
for(let j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] == 1 && i > 0 && j > 0) {
matrix[i][j] = Math.min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1
}
res += matrix[i][j]
}
}
return res
};
Top comments (2)
You just told the algorithm instead of talking about the intuition on how to come up with such algorithms, why are you even using minimum value of all but not maximum or diagonal value?
what are your observations generally for questions like these? This is so neat