Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1277.html
1277. Count Square Submatrices with All Ones (Medium)
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.
Example 2:
Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7.
Constraints:
1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1
Related Topics:
Array, Dynamic Programming
Solution 1. DP
Let dp[i][j]
be the side length of the max square with all ones.
dp[i + 1][j + 1] = min( dp[i][j], dp[i + 1][j], dp[i][j + 1] ) + 1
dp[0][i] = dp[i][0] = 0
The answer is the sum of all dp[i + 1][j + 1]
.
// OJ: https://leetcode.com/problems/count-square-submatrices-with-all-ones/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int countSquares(vector<vector<int>>& A) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<vector<int>> dp(M + 1, vector<int>(N + 1));
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (A[i][j] == 0) continue;
dp[i + 1][j + 1] = min({ dp[i][j], dp[i + 1][j], dp[i][j + 1] }) + 1;
ans += dp[i + 1][j + 1];
}
}
return ans;
}
};
Solution 2. DP
// OJ: https://leetcode.com/problems/count-square-submatrices-with-all-ones/
// Time: O(MN)
// Space: O(N)
class Solution {
public:
int countSquares(vector<vector<int>>& A) {
int M = A.size(), N = A[0].size(), ans = 0;
vector<int> dp(N + 1);
for (int i = 0; i < M; ++i) {
int prev = 0;
for (int j = 0; j < N; ++j) {
int cur = dp[j + 1];
if (A[i][j] == 0) dp[j + 1] = 0;
else dp[j + 1] = min({ prev, dp[j], dp[j + 1] }) + 1;
ans += dp[j + 1];
prev = cur;
}
}
return ans;
}
};
-
class Solution { public int countSquares(int[][] matrix) { int rows = matrix.length, columns = matrix[0].length; boolean[][] flags = new boolean[rows][columns]; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) flags[i][j] = true; } int count = 0; int maxSide = Math.min(rows, columns); for (int side = 1; side <= maxSide; side++) { int rowEnd = rows - side, columnEnd = columns - side; for (int i = 0; i <= rowEnd; i++) { int fromRow = i, toRow = i + side - 1; for (int j = 0; j <= columnEnd; j++) { if (!flags[i][j]) continue; int fromColumn = j, toColumn = j + side - 1; boolean isAllOne = true; outer: for (int row = fromRow; row <= toRow; row++) { for (int column = fromColumn; column <= toColumn; column++) { if (matrix[row][column] != 1) { flags[i][j] = false; isAllOne = false; break outer; } } } if (isAllOne) count++; } } } return count; } } ############ class Solution { public int countSquares(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; int[][] f = new int[m][n]; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == 0) { continue; } if (i == 0 || j == 0) { f[i][j] = 1; } else { f[i][j] = Math.min(f[i - 1][j - 1], Math.min(f[i - 1][j], f[i][j - 1])) + 1; } ans += f[i][j]; } } return ans; } }
-
// OJ: https://leetcode.com/problems/count-square-submatrices-with-all-ones/ // Time: O(MN) // Space: O(MN) class Solution { public: int countSquares(vector<vector<int>>& A) { int M = A.size(), N = A[0].size(), ans = 0; vector<vector<int>> dp(M + 1, vector<int>(N + 1)); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (A[i][j] == 0) continue; dp[i + 1][j + 1] = min({ dp[i][j], dp[i + 1][j], dp[i][j + 1] }) + 1; ans += dp[i + 1][j + 1]; } } return ans; } };
-
class Solution: def countSquares(self, matrix: List[List[int]]) -> int: m, n = len(matrix), len(matrix[0]) f = [[0] * n for _ in range(m)] ans = 0 for i, row in enumerate(matrix): for j, v in enumerate(row): if v == 0: continue if i == 0 or j == 0: f[i][j] = 1 else: f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1 ans += f[i][j] return ans
-
func countSquares(matrix [][]int) int { m, n, ans := len(matrix), len(matrix[0]), 0 f := make([][]int, m) for i := range f { f[i] = make([]int, n) } for i, row := range matrix { for j, v := range row { if v == 0 { continue } if i == 0 || j == 0 { f[i][j] = 1 } else { f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1 } ans += f[i][j] } } return ans } func min(a, b int) int { if a < b { return a } return b }