Scale Engineer

Number of Submatrices That Sum to Target

Hard
#1023Time: 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.1 company
Patterns
Prefix Sum
Data structures
ArrayHash TableMatrix
Companies
Media.net

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem