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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Submatrices That Sum to Target

Number: 1145

Difficulty: Hard

Paid? No

Companies: Google, Meta, Amazon

Problem Description

Given a matrix and an integer target, count the number of non-empty submatrices whose elements sum exactly to target. A submatrix is defined by the coordinates (x1, y1, x2, y2) covering all cells matrix[x][y] for x1 ≤ x ≤ x2 and y1 ≤ y ≤ y2.

Key Insights

  • Transform the 2D submatrix sum problem into multiple 1D subarray sum problems.
  • Precompute cumulative sums by fixing two row boundaries and then summing columns between these rows.
  • Use a hash table (or dictionary) to count the number of subarrays with a given sum, reducing the problem to the classic "subarray sum equals k" question.
  • Iterate over all possible row pairs and for each, treat the column sums as an array where the target sum is sought.

Space and Time Complexity

Time Complexity: O(n² * m), where n is the number of rows and m is the number of columns. Space Complexity: O(m), used by the hash table for storing cumulative sums along the columns.

Solution

The idea is to iterate over all pairs of rows (top and bottom) and, for each pair, compute the cumulative column sums between these rows. This converts the problem into finding the number of subarrays in a one-dimensional array (the column sums) that add up to the target. For each such 1D problem, use a hash table to track the frequency of cumulative sums seen so far and count how many times the difference (current sum - target) has been seen. This count gives the number of subarrays ending at the current index which sum to target. Combining counts from all possible row pairs yields the final result.

Code Solutions

# Python solution for counting number of submatrices that sum to target

def numSubmatrixSumTarget(matrix, target):
    # Dimensions of the matrix
    n = len(matrix)
    m = len(matrix[0])
    result = 0
    
    # Loop over all possible starting rows
    for top in range(n):
        # Initialize a list to store the column sums between row 'top' and 'bottom'
        col_sums = [0] * m
        
        # Extend the submatrix from row 'top' downwards to 'bottom'
        for bottom in range(top, n):
            # Update column sums for the current bottom row
            for col in range(m):
                col_sums[col] += matrix[bottom][col]
            
            # Use a dictionary to count cumulative sums in the 1D array (col_sums)
            sum_count = {0: 1}
            curr_sum = 0
            # Iterate over each column in col_sums to find the number of subarrays with sum equal to target
            for value in col_sums:
                curr_sum += value
                if (curr_sum - target) in sum_count:
                    result += sum_count[curr_sum - target]
                # Update the dictionary with the current sum count
                sum_count[curr_sum] = sum_count.get(curr_sum, 0) + 1
    
    return result

# Example usage:
if __name__ == "__main__":
    matrix = [[0, 1, 0], [1, 1, 1], [0, 1, 0]]
    target = 0
    print(numSubmatrixSumTarget(matrix, target))  # Expected Output: 4
← Back to All Questions