We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Submatrices That Sum to Target

Difficulty: Hard

Problem 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 are different if they have some coordinate that is different.

Key Insights

  • The problem can be approached using prefix sums to calculate the sum of submatrices efficiently.
  • We can iterate through all pairs of row indices and for each pair, treat the sum of columns as a 1D array.
  • Use a hash map to count the number of times each sum occurs while iterating through the columns, allowing us to find the target sum quickly.
  • The complexity comes from the nested loops over the rows combined with the use of a hash map to track sums.

Space and Time Complexity

Time Complexity: O(N^2 * M) where N is the number of rows and M is the number of columns in the matrix.
Space Complexity: O(M) for storing cumulative sums in the hash map.

Solution

To solve this problem, we will use a combination of prefix sums and a hash map. The idea is to iterate over all pairs of rows in the matrix, computing the cumulative sums for each column between the two rows. We then use a hash map to count how many times each cumulative sum appears. By checking if the difference between the cumulative sum and the target exists in the hash map, we can count valid submatrices that sum to the target.

Code Solutions

def numSubmatrixSumTarget(matrix, target):
    if not matrix or not matrix[0]:
        return 0
    
    row, col = len(matrix), len(matrix[0])
    count = 0
    
    for top in range(row):
        # Initialize a list to store the sum of columns
        sums = [0] * col
        
        for bottom in range(top, row):
            # Update the sums for the current bottom row
            for c in range(col):
                sums[c] += matrix[bottom][c]
            
            # Use a hash map to count the occurrences of sums
            sum_count = {0: 1}
            current_sum = 0
            
            for s in sums:
                current_sum += s
                # Check if there's a previous sum that matches current_sum - target
                count += sum_count.get(current_sum - target, 0)
                # Update the count of current_sum in the hash map
                sum_count[current_sum] = sum_count.get(current_sum, 0) + 1
                
    return count
← Back to All Questions