Skip to content

1074. Number of Submatrices That Sum to Target 👍

  • Time: $O(mn^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
    const int m = matrix.size();
    const int n = matrix[0].size();
    int ans = 0;

    // Transfer each row in the matrix to the prefix sum.
    for (auto& row : matrix)
      for (int i = 1; i < n; ++i)
        row[i] += row[i - 1];

    for (int baseCol = 0; baseCol < n; ++baseCol)
      for (int j = baseCol; j < n; ++j) {
        unordered_map<int, int> prefixCount{{0, 1}};
        int sum = 0;
        for (int i = 0; i < m; ++i) {
          if (baseCol > 0)
            sum -= matrix[i][baseCol - 1];
          sum += matrix[i][j];
          if (const auto it = prefixCount.find(sum - target);
              it != prefixCount.cend())
            ans += it->second;
          ++prefixCount[sum];
        }
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int numSubmatrixSumTarget(int[][] matrix, int target) {
    final int m = matrix.length;
    final int n = matrix[0].length;
    int ans = 0;

    // Transfer each row in the matrix to the prefix sum.
    for (int[] row : matrix)
      for (int i = 1; i < n; ++i)
        row[i] += row[i - 1];

    for (int baseCol = 0; baseCol < n; ++baseCol)
      for (int j = baseCol; j < n; ++j) {
        Map<Integer, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0, 1);
        int sum = 0;
        for (int i = 0; i < m; ++i) {
          if (baseCol > 0)
            sum -= matrix[i][baseCol - 1];
          sum += matrix[i][j];
          ans += prefixCount.getOrDefault(sum - target, 0);
          prefixCount.merge(sum, 1, Integer::sum);
        }
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def numSubmatrixSumTarget(self, matrix: list[list[int]], target: int) -> int:
    m = len(matrix)
    n = len(matrix[0])
    ans = 0

    # Transfer each row in the matrix to the prefix sum.
    for row in matrix:
      for i in range(1, n):
        row[i] += row[i - 1]

    for baseCol in range(n):
      for j in range(baseCol, n):
        prefixCount = collections.Counter({0: 1})
        summ = 0
        for i in range(m):
          if baseCol > 0:
            summ -= matrix[i][baseCol - 1]
          summ += matrix[i][j]
          ans += prefixCount[summ - target]
          prefixCount[summ] += 1

    return ans