Approach 1: Recursion + Memoization (Top-Down)
Consider each position {i,j} of the matrix to be the top-left corner of a square. If matrix[i][j] = 0, it does not form a square. If matrix[i][j] = 1, it forms a square of length 1. From this position, try extending length of the square by going right, bottom and diagonally (bottom right). Suppose the index to its right {i, j+1} forms a square of length 2, the index of its bottom {i+1, j} forms a square of length 2 and the index to its diagonal forms a square of length 1. Something like this:
Consider position {0,0}
1 1 1
1 1 1
1 1 0
Clearly, size of largest square formed by {0,0} as top left corner is 1, i.e., min({right, bottom, diagonal}). Note that number of squares with {0,0} as top-left corner = length of biggest square with {0,0} as top-left corner. In this case, first square is {0,0} on length 1 and second square of length 2 is enclosed between {0,0} and {1,1}.
class Solution {
public:
/*
* recursion + memo solution
* consider each position [i, j] as the top-left corner of square - we check to its right, bottom and diagonal (towards bottom right)
* size of square at [i, j] = min(right, bottom, diagonal)
* Also, a square of size 3 will have a square of size 2 and 1 also so just add the length of square to answer:
1 1 1
1 1 1
1 1 1
square starting at [0,0] is of length 3. The three squares with [0,0] as their top left corners are: [0,0] single element itself, 2x2 square enclosed by [0,0] and [1,1], 3x3 square enclosed by [0,0] and [2,2]
*/
int dp[301][301];
int dfs(vector<vector<int>>& A, int i, int j) {
if(i < 0 || j < 0 || i >= A.size() || j >= A[0].size() || A[i][j] != 1)
return 0;
if(dp[i][j] != -1)
return dp[i][j];
int ans = 1;
int l = dfs(A, i, j + 1), r = dfs(A, i + 1, j), t = dfs(A, i + 1, j + 1);
ans = 1 + min(l, min(r, t));
return dp[i][j] = ans;
}
int countSquares(vector<vector<int>>& A) {
int ans = 0;
int n = A.size(), m = A[0].size();
memset(dp, -1, sizeof dp);
for(int i = 0; i < A.size(); i++) {
for(int j = 0; j < A[i].size(); j++) {
if(A[i][j]) {
int sz = dfs(A, i, j);
ans += sz;
}
}
}
return ans;
}
};
Time complexity: O(n*n)
Approach 2: Dynamic Programming (Bottom-Up)
For a bottom-up approach using dynamic programming, we just need to reverse our above thinking. Consider each index {i,j} as the bottom right corner of a square. Define dp[i][j] as the size of biggest square with {i,j} as its bottom right corner. Clearly, if matrix[i][j] = 0, dp[i][j] = 0. If matrix[i][j] = 1, dp[i][j] = 1 + min(dp[i-1][j]
int countSquares(vector<vector<int>>& matrix) {
int rows = matrix.size();
if (!rows)
return 0;
int cols = matrix[0].size();
int count = 0;
for (int i=0; i<rows; i++) {
for (int j=0; j<cols; j++) {
if (matrix[i][j] == 1) {
count++;
if (i>0 && j>0)
matrix[i][j] = min(matrix[i-1][j], min(matrix[i-1][j-1], matrix[i][j-1])) + 1;
if (matrix[i][j] > 1)
count+=matrix[i][j]-1;
}
}
}
return count;
}
Time complexity: O(n*n)