# Number of Submatrices That Sum to Target
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-submatrices-that-sum-to-target)
Canonical: https://scaleengineer.com/dsa/problems/number-of-submatrices-that-sum-to-target
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table, Matrix
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net)
---
## Problem
Given a `matrix` and a `target`, return the number of non-empty submatrices that sum to target.

A submatrix `x1, y1, x2, y2` is the set of all cells `matrix[x][y]` with `x1 <= x <= x2` and `y1 <= y <= y2`.

Two submatrices `(x1, y1, x2, y2)` and `(x1', y1', x2', y2')` are different if they have some coordinate that is different: for example, if `x1 != x1'`.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-submatrices-that-sum-to-target/image0.jpg) 

**Input:** matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
**Output:** 4
**Explanation:** The four 1x1 submatrices that only contain 0.

**Example 2:**

**Input:** matrix = [[1,-1],[-1,1]], target = 0
**Output:** 5
**Explanation:** The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

**Example 3:**

**Input:** matrix = [[904]], target = 0
**Output:** 0

**Constraints:**

* `1 <= matrix.length <= 100`
* `1 <= matrix[0].length <= 100`
* `-1000 <= matrix[i][j] <= 1000`
* `-10^8 <= target <= 10^8`

# Approaches
## Brute Force Enumeration
This approach involves iterating through every possible submatrix, calculating the sum of its elements, and checking if the sum equals the target.
**Time:** O(R^3 * C^3), where R is the number of rows and C is the number of columns. There are O(R^2 * C^2) submatrices, and for each, the sum calculation can take up to O(R * C) time. · **Space:** O(1), as we only use a few variables to store sums and loop indices.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for larger inputs.
### Explanation
We define a submatrix by its top-left corner (r1, c1) and its bottom-right corner (r2, c2). We use four nested loops to iterate through all possible combinations of r1, c1, r2, and c2. For each defined submatrix, we use two more nested loops to iterate through its elements and calculate their sum. If the calculated sum matches the target, we increment a counter. This method is very intuitive but computationally expensive due to the six nested loops.

```java
class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int count = 0;

        // Iterate over all possible top-left corners (r1, c1)
        for (int r1 = 0; r1 < rows; r1++) {
            for (int c1 = 0; c1 < cols; c1++) {
                // Iterate over all possible bottom-right corners (r2, c2)
                for (int r2 = r1; r2 < rows; r2++) {
                    for (int c2 = c1; c2 < cols; c2++) {
                        // Calculate the sum of the submatrix defined by (r1, c1) and (r2, c2)
                        int sum = 0;
                        for (int i = r1; i <= r2; i++) {
                            for (int j = c1; j <= c2; j++) {
                                sum += matrix[i][j];
                            }
                        }
                        // Check if the sum equals the target
                        if (sum == target) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0.
*   Iterate through each possible starting row `r1` from 0 to `rows-1`.
*   Inside, iterate through each possible starting column `c1` from 0 to `cols-1`.
*   Inside, iterate through each possible ending row `r2` from `r1` to `rows-1`.
*   Inside, iterate through each possible ending column `c2` from `c1` to `cols-1`.
*   For each submatrix defined by `(r1, c1, r2, c2)`, calculate its sum by iterating from `r1` to `r2` and `c1` to `c2`.
*   If the sum equals `target`, increment `count`.
*   Return `count`.

## Optimized Sum Calculation with 2D Prefix Sum
This approach improves upon the brute-force method by pre-calculating a 2D prefix sum matrix. This allows us to find the sum of any submatrix in constant time, reducing the overall complexity.
**Time:** O(R^2 * C^2). Pre-computation takes O(R * C). The four nested loops to check every submatrix dominate the complexity. · **Space:** O(R * C) to store the 2D prefix sum matrix.
**Pros:** Significantly faster than the pure brute-force approach.; Reduces the sum calculation from O(R*C) to O(1).
**Cons:** Still too slow for the given constraints, as O(R^2 * C^2) is too large.; Uses extra space for the prefix sum matrix.
### Explanation
First, we create a `prefixSum` matrix of size `(rows + 1) x (cols + 1)`. `prefixSum[i][j]` will store the sum of the rectangle from `(0, 0)` to `(i-1, j-1)`. This `prefixSum` matrix can be computed in O(R * C) time using the formula: `prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]`. After the `prefixSum` matrix is built, we iterate through all possible submatrices using four nested loops, just like in the brute-force approach. However, instead of calculating the sum with two extra loops, we use the `prefixSum` matrix to get the sum in O(1) time. The sum of the submatrix from `(r1, c1)` to `(r2, c2)` is given by `prefixSum[r2+1][c2+1] - prefixSum[r1][c2+1] - prefixSum[r2+1][c1] + prefixSum[r1][c1]`. If this sum equals the target, we increment our count.

```java
class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int count = 0;

        // Create and compute the 2D prefix sum matrix
        int[][] prefixSum = new int[rows + 1][cols + 1];
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                prefixSum[i][j] = matrix[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
            }
        }

        // Iterate over all possible submatrices
        for (int r1 = 1; r1 <= rows; r1++) {
            for (int c1 = 1; c1 <= cols; c1++) {
                for (int r2 = r1; r2 <= rows; r2++) {
                    for (int c2 = c1; c2 <= cols; c2++) {
                        // Calculate sum in O(1) using prefix sum matrix
                        int sum = prefixSum[r2][c2] - prefixSum[r1 - 1][c2] - prefixSum[r2][c1 - 1] + prefixSum[r1 - 1][c1 - 1];
                        if (sum == target) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Create a 2D prefix sum matrix `prefixSum` of size `(rows+1) x (cols+1)`.
*   Populate `prefixSum` in O(R * C) time.
*   Initialize a counter `count` to 0.
*   Iterate through all possible top-left `(r1, c1)` and bottom-right `(r2, c2)` corners of submatrices.
*   For each submatrix, calculate its sum in O(1) using the `prefixSum` matrix.
*   If the sum equals `target`, increment `count`.
*   Return `count`.

## Optimal Approach: Reducing to 1D Subarray Sum
This is the most efficient approach. The core idea is to fix a pair of columns (a left column `c1` and a right column `c2`) and then treat the problem as finding the number of subarrays that sum to the target in a 1D array. This 1D array is formed by summing up the elements between `c1` and `c2` for each row.
**Time:** O(C^2 * R). We have two nested loops for columns (O(C^2)) and an inner loop for rows (O(R)). If R > C, we can optimize by iterating over rows first, making the complexity O(min(R, C)^2 * max(R, C)). · **Space:** O(R) to store the `rowSum` array and the HashMap. If we iterate over rows first (when R > C), it would be O(C). So, O(max(R, C)).
**Pros:** Most efficient approach that passes the given constraints.; Cleverly reduces a 2D problem to a series of 1D problems, which can be solved efficiently.
**Cons:** Can be less intuitive to come up with compared to the more direct approaches.
### Explanation
We iterate through all possible pairs of left and right columns, `c1` and `c2`. For each pair of columns, we create a 1D array, let's call it `rowSum`, where `rowSum[i]` stores the sum of elements in the i-th row from column `c1` to `c2`. We can build this `rowSum` array efficiently. We start with `c1` and iterate `c2` from `c1` to the last column. For each `c2`, we update the `rowSum` array by adding the elements of column `c2`. Now, for the current `rowSum` array, we need to solve the classic problem: "Find the number of subarrays that sum to `target`". This 1D problem can be solved in linear time using a HashMap. We iterate through `rowSum`, keeping track of the `currentPrefixSum`. For each `currentPrefixSum`, we check if `currentPrefixSum - target` exists in our HashMap. If it does, it means there's a subarray ending at the current position with the desired sum. The value in the map tells us how many such starting points exist. We initialize the map with a `(0, 1)` entry to handle subarrays that start from the beginning of `rowSum`. By summing up the counts from all pairs of columns, we get the total number of submatrices.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int count = 0;

        // Iterate over all possible pairs of columns
        for (int c1 = 0; c1 < cols; c1++) {
            int[] rowSum = new int[rows];
            for (int c2 = c1; c2 < cols; c2++) {
                // Update rowSum array for the current columns c1 to c2
                for (int r = 0; r < rows; r++) {
                    rowSum[r] += matrix[r][c2];
                }

                // Solve the 1D subarray sum problem for the current rowSum array
                Map<Integer, Integer> prefixSumCount = new HashMap<>();
                prefixSumCount.put(0, 1);
                int currentSum = 0;
                for (int sum : rowSum) {
                    currentSum += sum;
                    count += prefixSumCount.getOrDefault(currentSum - target, 0);
                    prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize `count = 0`.
*   Iterate through all possible left columns `c1` from `0` to `cols-1`.
*   For each `c1`, create a 1D array `rowSum` of size `rows`, initialized to zeros.
*   Iterate through all possible right columns `c2` from `c1` to `cols-1`.
    *   Update `rowSum` by adding the elements of column `c2`. Now `rowSum[r]` holds the sum of `matrix[r][c1...c2]`.
    *   Solve the 1D "subarray sum equals k" problem on `rowSum` using a HashMap.
    *   Initialize `map = {0: 1}` and `currentSum = 0`.
    *   Iterate through `rowSum`:
        *   Update `currentSum`.
        *   Add `map.getOrDefault(currentSum - target, 0)` to the total `count`.
        *   Increment the frequency of `currentSum` in the map.
*   Return `count`.

# Solutions
### Java

```java
class Solution {
public
  int numSubmatrixSumTarget(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      int[] col = new int[n];
      for (int j = i; j < m; ++j) {
        for (int k = 0; k < n; ++k) {
          col[k] += matrix[j][k];
        }
        ans += f(col, target);
      }
    }
    return ans;
  }
private
  int f(int[] nums, int target) {
    Map<Integer, Integer> d = new HashMap<>();
    d.put(0, 1);
    int s = 0, cnt = 0;
    for (int x : nums) {
      s += x;
      cnt += d.getOrDefault(s - target, 0);
      d.merge(s, 1, Integer : : sum);
    }
    return cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      vector<int> col(n);
      for (int j = i; j < m; ++j) {
        for (int k = 0; k < n; ++k) {
          col[k] += matrix[j][k];
        }
        ans += f(col, target);
      }
    }
    return ans;
  }
  int f(vector<int> &nums, int target) {
    unordered_map<int, int> d{{0, 1}};
    int cnt = 0, s = 0;
    for (int &x : nums) {
      s += x;
      if (d.count(s - target)) {
        cnt += d[s - target];
      }
      ++d[s];
    }
    return cnt;
  }
};

```

### Python

```python
class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int: def f(nums: List[int]) -> int: d = defaultdict(int) d[0] = 1 cnt = s = 0 for x in nums: s += x cnt += d[s - target] d[s] += 1 return cnt m, n = len(matrix), len(matrix[0]) ans = 0 for i in range(m): col = [0] * n for j in range(i, m): for k in range(n): col[k] += matrix[j][k] ans += f(col) return ans

```