Sponsored
Sponsored
The dynamic programming approach involves creating a DP array where each element represents the size of the largest square submatrix ending at that element. We'll only consider elements that are 1s, as 0s can't be part of a square of 1s. For each element that is 1, it can be the bottom-right corner of a square submatrix; we consider the minimum of the sizes of squares ending directly above, to the left, and diagonally above and to the left of it, then add 1 to this value. Sum up all the values in the DP array to get the total count of square submatrices.
Time Complexity: O(m * n), where m and n are the number of rows and columns in the matrix, respectively.
Space Complexity: O(m * n), due to the auxiliary DP matrix used to store maximum square sizes at each point.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int countSquares(vector<vector<int>>& matrix) {
6 int m = matrix.size();
7 if (m == 0) return 0;
8 int n = matrix[0].size();
9 vector<vector<int>> dp(m, vector<int>(n, 0));
10 int count = 0;
11 for (int i = 0; i < m; ++i) {
12 for (int j = 0; j < n; ++j) {
13 if (matrix[i][j] == 0) continue;
14 if (i == 0 || j == 0) {
dp[i][j] = matrix[i][j];
} else {
dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
}
count += dp[i][j];
}
}
return count;
}This C++ solution uses the same dynamic programming approach. It initializes a 2D dp vector to accumulate counts of squares ending at each cell and employs STL's min function to easily calculate the smallest neighboring submatrix size. The result is accumulated and returned as the total count of square submatrices.