Number of Submatrices That Sum to Target

class Solution {
  public int countSubmatricesWithSum(int[][] grid, int goal) {
    int rows = grid.length, cols = grid[0].length;
    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] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + grid[i - 1][j - 1];
      }
    }
    
    int result = 0, sum;
    Map<Integer, Integer> countMap = new HashMap<>();
    for (int colStart = 1; colStart <= cols; ++colStart) {
      for (int colEnd = colStart; colEnd <= cols; ++colEnd) {
        countMap.clear();
        countMap.put(0, 1);
        for (int r = 1; r <= rows; ++r) {
          sum = prefixSum[r][colEnd] - prefixSum[r][colStart - 1];
          result += countMap.getOrDefault(sum - goal, 0);
          countMap.put(sum, countMap.getOrDefault(sum, 0) + 1);
        }
      }
    }
    
    return result;
  }
}

The provided Java solution tackles the problem of counting the number of submatrices within a given matrix that sum up to a specified target. This solution utilizes an efficient approach by leveraging a prefix sum array combined with hash mapping to streamline the calculation of submatrix sums.

• Firstly, a prefixSum 2D array is constructed for the input grid to obtain the cumulative sum up to any (i, j) point in constant time. This facilitates the rapid calculation of any submatrix sum.
• The algorithm iterates through all possible pairs of starting and ending columns. For each pair of columns, it resets and uses a HashMap (referred to as countMap in the code) to track the frequency of cumulative row sums encountered thus far.
• For every row, the difference between the current row's cumulative sum at colEnd and colStart-1 is calculated to determine the cumulative sum of the submatrix bounded by these columns.
• Using countMap, the algorithm checks how often the sum of the current row and the previous rows equals sum - goal. If such a sum has been encountered before, it indicates that a submatrix ending at the current row and within the column bounds sums to the target, and the count of such submatrices is incremented accordingly.
• This approach's efficiency is derived from reducing the problem complexity by fixing column bounds and sequentially accumulating and checking row sums.

In practice, ensure to consider edge cases such as empty grids or grids with non-uniform row/column lengths which might not fit this specific implementation strategy directly. By using both spatial (prefix sum) and temporal (hash map frequency counts) optimization, the solution achieves significant efficiency suitable for large matrices.

from collections import defaultdict
class Solution:
    def numberOfSubmatricesWithSum(self, mat: List[List[int]], goal: int) -> int:
        rows, cols = len(mat), len(mat[0])
            
        # Calculate 2D prefix sums to help with submatrix sums
        prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1] + mat[i - 1][j - 1]
            
        total_count = 0
        # Consider all possible column pairs and count submatrices with target sum using hashmap
        for start_col in range(1, cols + 1):
            for end_col in range(start_col, cols + 1):
                sums = defaultdict(int)
                sums[0] = 1
                    
                for row in range(1, rows + 1):
                    # Compute the current prefix sum for the fixed columns
                    current_pref = prefix_sum[row][end_col] - prefix_sum[row][start_col - 1]
                        
                    # Count submatrices that reach the goal
                    total_count += sums[current_pref - goal]
                        
                    # Store the current prefix sum in the hashmap
                    sums[current_pref] += 1
                        
        return total_count

To solve the problem of counting the number of submatrices with a sum equal to a specific target within a 2D matrix using Python, follow the approach outlined below:

• Calculate the prefix sums for the matrix. This helps in quickly calculating the sum of any submatrix. Initialize a 2D list prefix_sum where the entry at i,j is the sum of the submatrix from the top-left corner to the position i-1,j-1 in the original matrix.

• Utilize a hash map for optimization. As we iterate through every possible pair of columns, we use the hashmap sums to keep track of the various sums encountered so far across the rows. The key idea is to store how often each sum appears up to the current row. This allows you to quickly determine how many times you've seen the current submatrix sum minus the goal. This difference gives the count of submatrices ending at the current row that add up to the target sum.

Follow this methodology to implement the solution:

1. Compute 2D prefix sums for the matrix. For each cell in the matrix, compute the cumulative sums using both top and left cells, subtracting the overlap to avoid double counting.

2. Iterate through all pairs of columns. For each pair, reset your sums hash map, setting the count for a sum of 0 to 1 to account for perfect matches from the start of the matrix.

3. As you iterate through each row, compute the submatrix sum from the start row to the current row for the column pair.

4. Check how many times the current sum minus the goal sum has been encountered (indicative of submatrices that sum up to the goal from previous rows).

5. Update the hashmap with the current sum for updating future iterations.

This approach highlights effective use of both prefix sums and hashmaps to solve a potentially computationally expensive problem of finding submatrix sums efficiently.