Skip to content

1277. Count Square Submatrices with All Ones 👍

  • Time: $O(mn)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class 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 subtotal, const vector<int>& row) {
      return subtotal + accumulate(row.begin(), row.end(), 0);
    });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
  public int countSquares(int[][] matrix) {
    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]));
    return Arrays.stream(matrix).flatMapToInt(Arrays::stream).sum();
  }
}

1
2
3
4
5
6
7
8
class 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(map(sum, matrix))