Count Square Submatrices with All Ones

Leetcode Problem:

• Count Square Submatrices with All Ones

Summary

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

Approach

• Dynamic programming is used to solve this problem
• A 2D array dp is created to store the size of the largest square submatrix ending at each cell
• The solution is calculated by iterating through the matrix and updating the dp array
• The size of the largest square submatrix ending at each cell is calculated by taking the minimum of the sizes of the largest square submatrices ending at the cell above, the cell to the left, and the cell to the top-left, and adding 1 to it.

Complexity

• O(m*n) where m and n are the number of rows and columns in the matrix respectively.

Explanation

• The solution starts by initializing a 2D array dp of size 301x301 with all elements set to 0
• Then it iterates through the matrix
• If the current cell is 0, it skips it
• If the current cell is 1, it calculates the size of the largest square submatrix ending at the current cell by taking the minimum of the sizes of the largest square submatrices ending at the cell above, the cell to the left, and the cell to the top-left, and adds 1 to it
• The size of the largest square submatrix ending at the current cell is then stored in the dp array
• Finally, the solution is calculated by summing up the values in the dp array.

Solution Code:

class Solution {
public:
    int countSquares(vector>& matrix) {
        int dp[301][301] = {0};
        int res = 0;
        for(int i = 0 ; i < matrix.size(); i++){
            for(int j = 0 ; j < matrix[i].size();j++){
                if(matrix[i][j] == 0){
                    continue;
                }
                if(i-1 < 0 || j-1 < 0){
                    dp[i][j] = matrix[i][j];
                    res += dp[i][j];
                    continue;
                }
                dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1], dp[i][j-1])) + 1;
                res += dp[i][j];
            }
        }
        
        return res;
    }
};