Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

1074. Number of Submatrices That Sum to Target

Time: $O(mn^2)$

Space: $O(n)$

			


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 of matrix to 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 (prefixCount.count(sum - target))
            ans += prefixCount[sum - target];
          ++prefixCount[sum];
        }
      }

    return ans;
  }
};




			


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 of matrix to 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.put(sum, prefixCount.getOrDefault(sum, 0) + 1);
        }
      }

    return ans;
  }
}




			


class Solution:
  def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
    m = len(matrix)
    n = len(matrix[0])
    ans = 0

    # Transfer each row of matrix to 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 = 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