loading...

Count Square Submatrices with All Ones - Leet Code

chakrihacker profile image Subramanya Chakravarthy ・2 min read

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.

Continuous Square Sub Matrices

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:

  1. Initialize a result matrix to add up square matrices as encountered
  2. Loop through each element matrix[i][j] and check the maximum square can be formed at that point
  3. 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
};

Discussion

markdown guide
 

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