1277. Count Square Submatrices with All Ones ¶ Time: $O(mn)$ Space: $O(1)$ C++JavaPython 1 2 3 4 5 6 7 8 9 10 11 12 13 14class Solution { public: int countSquares(vector<vector<int>>& matrix) { for (int i = 0; i < matrix.size(); ++i) for (int j = 0; j < matrix[0].size(); ++j) if (matrix[i][j] == 1 && i > 0 && j > 0) matrix[i][j] += min({matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1]}); return accumulate(matrix.begin(), matrix.end(), 0, [](int a, const auto& A) { return a + accumulate(A.begin(), A.end(), 0); }); } }; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15class Solution { public int countSquares(int[][] matrix) { int ans = 0; for (int i = 0; i < matrix.length; ++i) for (int j = 0; j < matrix[0].length; ++j) { if (matrix[i][j] == 1 && i > 0 && j > 0) matrix[i][j] += Math.min(matrix[i - 1][j - 1], Math.min(matrix[i - 1][j], matrix[i][j - 1])); ans += matrix[i][j]; } return ans; } } 1 2 3 4 5 6 7 8class Solution: def countSquares(self, matrix: List[List[int]]) -> int: for i in range(len(matrix)): for j in range(len(matrix[0])): if matrix[i][j] == 1 and i > 0 and j > 0: matrix[i][j] += min(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1]) return sum(sum(row) for row in matrix)