Welcome to Subscribe On Youtube
1277. Count Square Submatrices with All Ones
Description
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
Solutions
-
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; } }
-
class Solution { public: int countSquares(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); int ans = 0; vector<vector<int>> f(m, vector<int>(n)); 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] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1; ans += f[i][j]; } } 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 }