Code Implementation

class Solution:
    def numSubmatrixSumTarget(self, matrix, target):
        from collections import defaultdict
        m, n = len(matrix), len(matrix[0])
        # Precompute prefix sums for each row
        for row in matrix:
            for j in range(1, n):
                row[j] += row[j - 1]
        res = 0
        # For each pair of columns, use hashmap to count subarrays
        for start_col in range(n):
            for end_col in range(start_col, n):
                counter = defaultdict(int)
                counter[0] = 1
                curr_sum = 0
                for i in range(m):
                    # Sum of elements in row i between columns start_col and end_col
                    curr = matrix[i][end_col]
                    if start_col > 0:
                        curr -= matrix[i][start_col - 1]
                    curr_sum += curr
                    res += counter[curr_sum - target]
                    counter[curr_sum] += 1
        return res
      

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        // Precompute prefix sums for each row
        for (int i = 0; i < m; ++i)
            for (int j = 1; j < n; ++j)
                matrix[i][j] += matrix[i][j - 1];
        int res = 0;
        // For each pair of columns, use hashmap to count subarrays
        for (int start_col = 0; start_col < n; ++start_col) {
            for (int end_col = start_col; end_col < n; ++end_col) {
                unordered_map<int, int> counter;
                counter[0] = 1;
                int curr_sum = 0;
                for (int i = 0; i < m; ++i) {
                    int curr = matrix[i][end_col];
                    if (start_col > 0)
                        curr -= matrix[i][start_col - 1];
                    curr_sum += curr;
                    res += counter[curr_sum - target];
                    counter[curr_sum]++;
                }
            }
        }
        return res;
    }
};
      

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        // Precompute prefix sums for each row
        for (int i = 0; i < m; i++)
            for (int j = 1; j < n; j++)
                matrix[i][j] += matrix[i][j - 1];
        int res = 0;
        // For each pair of columns, use hashmap to count subarrays
        for (int start_col = 0; start_col < n; start_col++) {
            for (int end_col = start_col; end_col < n; end_col++) {
                Map<Integer, Integer> counter = new HashMap<>();
                counter.put(0, 1);
                int curr_sum = 0;
                for (int i = 0; i < m; i++) {
                    int curr = matrix[i][end_col];
                    if (start_col > 0)
                        curr -= matrix[i][start_col - 1];
                    curr_sum += curr;
                    res += counter.getOrDefault(curr_sum - target, 0);
                    counter.put(curr_sum, counter.getOrDefault(curr_sum, 0) + 1);
                }
            }
        }
        return res;
    }
}
      

var numSubmatrixSumTarget = function(matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    // Precompute prefix sums for each row
    for (let i = 0; i < m; i++) {
        for (let j = 1; j < n; j++) {
            matrix[i][j] += matrix[i][j - 1];
        }
    }
    let res = 0;
    // For each pair of columns, use hashmap to count subarrays
    for (let start_col = 0; start_col < n; start_col++) {
        for (let end_col = start_col; end_col < n; end_col++) {
            const counter = new Map();
            counter.set(0, 1);
            let curr_sum = 0;
            for (let i = 0; i < m; i++) {
                let curr = matrix[i][end_col];
                if (start_col > 0) curr -= matrix[i][start_col - 1];
                curr_sum += curr;
                res += (counter.get(curr_sum - target) || 0);
                counter.set(curr_sum, (counter.get(curr_sum) || 0) + 1);
            }
        }
    }
    return res;
};
      

Problem Description

Given a 2D matrix of integers called matrix and an integer target, your task is to count the number of submatrices (rectangular regions within the matrix) whose elements sum up exactly to target.

- Each submatrix must be contiguous and can be any size from 1x1 up to the full matrix.
- The elements of the matrix can be positive, negative, or zero.
- The same element can be used in multiple submatrices (since submatrices can overlap), but each submatrix is counted separately.
- The output should be the total number of such submatrices.

Thought Process

At first glance, the problem suggests trying all possible submatrices and checking if their sum equals target. However, this brute-force approach would involve four nested loops (for every possible top, bottom, left, and right boundary), making it computationally expensive for larger matrices.

To optimize, consider reducing the problem to a well-known 1D problem: counting subarrays with a given sum. If we fix two columns, the sum over each row between those columns becomes a 1D array. Then, the problem turns into finding the number of subarrays (contiguous rows) whose sum equals target.

This conceptual shift allows us to use prefix sums and hash maps to efficiently count valid submatrices, leveraging fast lookups and cumulative sum properties.

Solution Approach

The optimized solution involves several key steps:

• 1. Precompute Row Prefix Sums:
  For each row, calculate the prefix sum so that the sum of any segment of a row can be retrieved in constant time.
• 2. Iterate Over All Column Pairs:
  For every possible pair of columns (start_col and end_col), treat the sum of elements between these columns for each row as a 1D array.
• 3. Reduce to 1D Subarray Sum Problem:
  For each column pair, create a running sum over the rows. Use a hash map to count how many times a particular cumulative sum has occurred.
• 4. Use Hash Map for Fast Counting:
  For each row, compute the current cumulative sum and check if curr_sum - target has been seen before. If so, increment the result by the count stored in the hash map.
• 5. Accumulate the Result:
  Repeat this process for all column pairs and sum the results to get the final answer.

Example Walkthrough

Input:
matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0

Let's walk through the process:

• Step 1: Compute Row Prefix Sums
  After this step, each row shows the cumulative sum from the start of the row up to each column.
• Step 2: Iterate Over Column Pairs
  For each pair of columns (e.g., columns 0 to 0, 0 to 1, 0 to 2, 1 to 1, etc.), we build a 1D array representing the sum of elements in each row between those columns.
• Step 3: For Each Column Pair, Count Subarrays with Target Sum
  Use a hash map to count how many times a cumulative sum minus the target has been seen. Each time we find such a sum, it means a submatrix ending at the current row sums to the target.
• Step 4: Accumulate
  Repeat for all column pairs and sum up the counts.

Time and Space Complexity

Brute-Force Approach:
- Four nested loops (top, bottom, left, right), and sum calculation for each submatrix: O(m² n²) submatrices, each taking O(mn) to sum → O(m³ n³) total.

Optimized Approach:
- Two nested loops for columns (O(n²)), and for each, a single pass over rows (O(m)), with hash map operations (amortized O(1)):
- Total time: O(n² m)
- Space: O(m) for the hash map and O(mn) for storing prefix sums.

This is a significant improvement over the brute-force method.

Summary

The key insight is to transform the 2D submatrix sum problem into a series of 1D subarray sum problems by fixing pairs of columns and leveraging prefix sums. Using a hash map to count previous cumulative sums allows for efficient detection of submatrices matching the target sum. This approach is both elegant and efficient, making it suitable for large matrices and diverse input values.