Number of Submatrices That Sum to Target

Problem:

Given a matrix, and a target, return the number of non-empty submatrices that sum to target.

For example, given matrix
{
{0, 1},
{0, 1}
}
and target 0, the output should be 3.
Given the same matrix and target 1, the output should be 4.
Given the same matrix and target 2, the output should be 2.
Given the same matrix and target 3, the output should be 0.

Solution:
We have solved Subarray Sum Equals K before, this problem can be converted to that problem then get solved. The matrix involved in Subarray Sum Equals K is a 1D array, while we are dealing with 2D array here.

We can calculate the prefix sum of the original array, then any submatrices' sum can be calculated with from the prefix sum matrix. curr_sum = sum[r2][col] - sum[r1 - 1][col]. In 2D the prefix sum is a sum of the current value with the integers above or on the left.

prefix sum

For example:

              0 0 0
0 1         0 0 1
0 1         0 0 2


Now we can write the code

import java.util.*;
class Solution {
  public static void main(String...args) {
    int[][] arr = new int[][]
                            {
                            {0, 1},
                            {0, 1}
                            };
    int target = 0;
    System.out.println(numOfsubArrays(arr, target));
    target = 1;
    System.out.println(numOfsubArrays(arr, target));
    target = 2;
    System.out.println(numOfsubArrays(arr, target));
    target = 3;
    System.out.println(numOfsubArrays(arr, target));
  }
 
  public static int numOfsubArrays(int[][] arr, int target) {//0
    int r = arr.length;   //2
    int c = arr[0].length;  //2
    int[][] sum = new int[r+1][c+1]; //sum matrix is bigger than the orginal max
    //fill the sum from index 1,1 to r,c, not filled cells remain 0.
    for(int i = 1; i < r+1; i++) {
      for(int j = 1; j < c+1; j++) {
        sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i-1][j-1];
      }
    }
    /*
    0 0 0
    0 0 1
    0 0 2
    */
    int count = 0;
    Map<Integer, Integer> vals = new HashMap<>();
    for(int i = 0; i < r; i++) {
      for(int j = i+1; j < r+1; j++) {
        //with fixed row, 2D Subarray Sum Equals K problem converts to 1D Subarray Sum Equals K
        vals.clear();
        for(int k = 0; k < c+1; k++) {  //k=0, so we can have val.put(0, 0)
          int delta = sum[j][k] - sum[i][k];
          count += vals.getOrDefault(delta - target, 0);
          vals.put(delta, vals.getOrDefault(delta, 0) + 1);
        }
      }
    }
    return count;
  }
}

The time complexity is O(RRC) for the 3 layered loop, the space complexity is O(RC) for the prefix sum matrix.

see also:
Subarray Sum Equals K