Number of Submatrices That Sum to Target

HARD

Description

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:

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

Checkout 3 different approaches to solve Number of Submatrices That Sum to Target. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: O(R^2 * C^2). Pre-computation takes O(R * C). The four nested loops to check every submatrix dominate the complexity.Space Complexity: O(R * C) to store the 2D prefix sum matrix.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Number of Submatrices That Sum to Target. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Number of Submatrices That Sum to Target

Patterns:

Prefix Sum

Data Structures:

ArrayHash TableMatrix

Companies:

Media.net |