Count Submatrices With All Ones - Leetcode Solution

Problem Statement:

Given a matrix of 0's and 1's, count all submatrices consisting of only 1's.

Solution:

The problem can be solved using dynamic programming approach by maintaining a matrix of the same size as the input matrix to record the length of the largest continuous submatrix ending at (i, j) in the input matrix.

Let dp[i][j] be the length of the largest continuous submatrix with bottom-right corner at (i, j). The idea is to calculate dp[i][j] for each cell (i, j) in the input matrix. For any point (i, j) in the input matrix, if the value at that point is 0, then dp[i][j] = 0. If the value at that point is 1, then dp[i][j] can be calculated as follows:

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

The above formula calculates the length of the largest continuous submatrix ending at (i, j) by taking the minimum of the length of the largest continuous submatrix ending at (i - 1, j), (i, j - 1), and (i - 1, j - 1), and adding 1 to it.

The total count of submatrices can be calculated by summing up the dp values for all points (i, j) in the input matrix.

Pseudo code:

1. Initialize a variable called “count” to 0
2. Construct a matrix called “dp” of the same size as the input matrix and initialize it to 0
3. Loop through each row i in the input matrix and loop through each column j in that row
4. If the value at input matrix position (i, j) is 0, set dp[i][j] = 0
5. If the value at input matrix position (i, j) is 1, calculate dp[i][j] using the formula dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
6. Add the value in dp[i][j] to “count”
7. Return “count”

Time Complexity: O(mn), where m and n are the dimensions of the input matrix.

Space Complexity: O(mn), where m and n are the dimensions of the input matrix.

Code:

class Solution { public: int countSubmat(vector<vector<int>>& mat) { int count = 0; int m = mat.size(), n = mat[0].size(); vector<vector<int>> dp(m, vector<int>(n, 0));

    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(mat[i][j] == 1){
                dp[i][j] = 1;
                if(i > 0 && j > 0)
                    dp[i][j] += min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                count += dp[i][j];
            }
        }
    }
    return count;
}

};

1