Jobs

Interviews

Discussions

Number of Submatrices That Sum to Target

Hard

Asked by:

51 views

Topics:

ArraysDynamic Programming

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

Try coding it in LeetCode

Number of Submatrices That Sum to Target

Hard

Asked by:

51 views

Topics:

ArraysDynamic Programming

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the dimensions of the matrix (number of rows and columns), and what is the maximum size of the matrix overall?
Can the elements within the matrix be negative, zero, or only positive integers?
What are the constraints on the target value? Can the target be negative, zero, or only positive?
If no submatrix sums to the target, what should the function return? (e.g., 0, -1, null)
Are overlapping submatrices counted as distinct, or are we only counting unique sets of row/column boundaries?

Brute Force Solution

Approach

We need to find all rectangular blocks of numbers within a bigger grid that add up to a specific target value. The brute force approach tries every possible rectangular block, no matter how big or small, and checks if its numbers sum up to the target.

Here's how the algorithm would work step-by-step:

First, consider every possible starting corner for a rectangular block within the grid.
From each starting corner, try every possible width and height for the rectangular block.
For each rectangular block you define, calculate the sum of all the numbers inside it.
Compare the sum of the numbers in the rectangular block with the target value.
If the sum equals the target value, count it as a valid submatrix.
Repeat these steps for every possible starting corner, width, and height until you have examined all possible rectangular blocks.
The final count is the total number of submatrices whose sum matches the target.

Code Implementation

def num_submatrices_that_sum_to_target(matrix, target):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    count = 0

    for top_row in range(number_of_rows):
        for left_column in range(number_of_columns):
            # Iterate to define the submatrix's size
            for bottom_row in range(top_row, number_of_rows):
                for right_column in range(left_column, number_of_columns):
                    submatrix_sum = 0
                    
                    # Calculate sum of elements in the submatrix
                    for row_index in range(top_row, bottom_row + 1):
                        for column_index in range(left_column, right_column + 1):
                            submatrix_sum += matrix[row_index][column_index]

                    if submatrix_sum == target:
                        count += 1

    return count

Big(O) Analysis

Time Complexity

O(m^3 * n^3) – The provided solution considers every possible submatrix within the given matrix. Let 'm' be the number of rows and 'n' be the number of columns in the matrix. There are O(m * n) possible starting corners. For each starting corner, we iterate through all possible widths (up to n) and heights (up to m). This leads to O(m * n) combinations of width and height for each starting corner. For each submatrix defined by the corner, width, and height, calculating the sum of its elements takes O(m * n) time. Thus the total time complexity is O(m * n) * O(m * n) * O(m * n) = O(m^3 * n^3).

Space Complexity

O(1) – The provided brute force solution iterates through all possible submatrices by varying the starting corner, width, and height. It calculates the sum of each submatrix on the fly without storing any intermediate submatrix sums or other data structures related to the matrix elements themselves. Therefore, the auxiliary space used consists only of a few integer variables for loop indices and the current submatrix sum, which is constant regardless of the input matrix size, leading to O(1) space complexity.

Optimal Solution

Approach

The core idea is to calculate sums of rectangles very quickly. We achieve this by pre-calculating the sum of all rectangles starting from the top-left corner. This pre-calculation then lets us find the sum of *any* rectangle using only a few simple operations.

Here's how the algorithm would work step-by-step:

First, create a new table where each cell contains the sum of all the numbers in the rectangle from the top-left corner of the original table to that cell.
Now, go through all possible top and bottom rows of a submatrix.
For each pair of top and bottom rows, calculate the sums of all possible submatrices that start at the top row and end at the bottom row. To do this we loop through all possible left and right columns.
To calculate each submatrix sum, we use the pre-calculated table to get this sum very fast. No nested loops required.
If the submatrix sum equals our target, increase our count.
Return the final count.

Code Implementation

def num_submatrix_sum_target(matrix, target):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    # Create a prefix sum matrix.
    prefix_sum_matrix = [[0] * (number_of_columns + 1) for _ in range(number_of_rows + 1)]
    for row_index in range(1, number_of_rows + 1):
        for column_index in range(1, number_of_columns + 1):
            prefix_sum_matrix[row_index][column_index] = prefix_sum_matrix[row_index - 1][column_index] +\
                                        prefix_sum_matrix[row_index][column_index - 1] -\
                                        prefix_sum_matrix[row_index - 1][column_index - 1] +\
                                        matrix[row_index-1][column_index-1]

    count = 0
    # Iterate through all possible top and bottom rows.
    for top_row_index in range(1, number_of_rows + 1):
        for bottom_row_index in range(top_row_index, number_of_rows + 1):
            
            # Calculate submatrix sums and count.
            for left_column_index in range(1, number_of_columns + 1):
                for right_column_index in range(left_column_index, number_of_columns + 1):
                    
                    # Use prefix sums to calculate submatrix sum.
                    submatrix_sum = prefix_sum_matrix[bottom_row_index][right_column_index] -\
                                      prefix_sum_matrix[top_row_index - 1][right_column_index] -\
                                      prefix_sum_matrix[bottom_row_index][left_column_index - 1] +\
                                      prefix_sum_matrix[top_row_index - 1][left_column_index - 1]
                    
                    # Increment count if submatrix sum equals target.
                    if submatrix_sum == target:
                        count += 1

    return count

Big(O) Analysis

Time Complexity

O(m*m*n) – The algorithm first calculates the prefix sum of the matrix, which takes O(m*n) where m is the number of rows and n is the number of columns. Then, it iterates through all possible pairs of top and bottom rows, which takes O(m*m). For each pair of rows, it iterates through all possible left and right columns to calculate the submatrix sum using the prefix sums in O(n). Therefore, the overall time complexity is O(m*m*n).

Space Complexity

O(M*N) – The dominant space complexity comes from creating a prefix sum table of the same dimensions as the input matrix, where M is the number of rows and N is the number of columns. This table stores the cumulative sums, thus requiring M*N integer storage. No other significant data structures are created that scale with the input size. Therefore, the auxiliary space complexity is O(M*N).

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0 immediately as there are no submatrices to consider.
Matrix with only one row or one column	The algorithm should still function correctly, effectively reducing to a 1D prefix sum problem.
Large matrix dimensions (potential for memory issues)	The solution must be efficient in space and time complexity to avoid memory limits exceeded errors.
Matrix containing all zeros	The code must correctly count submatrices that sum to zero if the target is also zero.
Matrix with all negative numbers and a positive target	The code must return 0 since no submatrix can sum to a positive value.
Target value is extremely large, potentially causing integer overflow during sums	Use appropriate data types (long) to prevent potential integer overflows during submatrix sum calculations.
Target is zero and matrix contains both positive and negative numbers.	The solution should accurately count submatrices summing to zero considering both positive and negative values.
No submatrix sums to the target value	The algorithm should correctly return 0 when no matching submatrix is found.

Null or empty matrix

How to Handle:

Return 0 immediately as there are no submatrices to consider.

Matrix with only one row or one column

How to Handle:

The algorithm should still function correctly, effectively reducing to a 1D prefix sum problem.

Large matrix dimensions (potential for memory issues)

How to Handle:

The solution must be efficient in space and time complexity to avoid memory limits exceeded errors.

Matrix containing all zeros

How to Handle:

The code must correctly count submatrices that sum to zero if the target is also zero.

Matrix with all negative numbers and a positive target

How to Handle:

The code must return 0 since no submatrix can sum to a positive value.

Target value is extremely large, potentially causing integer overflow during sums

How to Handle:

Use appropriate data types (long) to prevent potential integer overflows during submatrix sum calculations.

Target is zero and matrix contains both positive and negative numbers.

How to Handle:

The solution should accurately count submatrices summing to zero considering both positive and negative values.

No submatrix sums to the target value

How to Handle:

The algorithm should correctly return 0 when no matching submatrix is found.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the dimensions of the matrix (number of rows and columns), and what is the maximum size of the matrix overall?
Can the elements within the matrix be negative, zero, or only positive integers?
What are the constraints on the target value? Can the target be negative, zero, or only positive?
If no submatrix sums to the target, what should the function return? (e.g., 0, -1, null)
Are overlapping submatrices counted as distinct, or are we only counting unique sets of row/column boundaries?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider every possible starting corner for a rectangular block within the grid.
From each starting corner, try every possible width and height for the rectangular block.
For each rectangular block you define, calculate the sum of all the numbers inside it.
Compare the sum of the numbers in the rectangular block with the target value.
If the sum equals the target value, count it as a valid submatrix.
Repeat these steps for every possible starting corner, width, and height until you have examined all possible rectangular blocks.
The final count is the total number of submatrices whose sum matches the target.

Code Implementation

def num_submatrices_that_sum_to_target(matrix, target):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    count = 0

    for top_row in range(number_of_rows):
        for left_column in range(number_of_columns):
            # Iterate to define the submatrix's size
            for bottom_row in range(top_row, number_of_rows):
                for right_column in range(left_column, number_of_columns):
                    submatrix_sum = 0
                    
                    # Calculate sum of elements in the submatrix
                    for row_index in range(top_row, bottom_row + 1):
                        for column_index in range(left_column, right_column + 1):
                            submatrix_sum += matrix[row_index][column_index]

                    if submatrix_sum == target:
                        count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a new table where each cell contains the sum of all the numbers in the rectangle from the top-left corner of the original table to that cell.
Now, go through all possible top and bottom rows of a submatrix.
For each pair of top and bottom rows, calculate the sums of all possible submatrices that start at the top row and end at the bottom row. To do this we loop through all possible left and right columns.
To calculate each submatrix sum, we use the pre-calculated table to get this sum very fast. No nested loops required.
If the submatrix sum equals our target, increase our count.
Return the final count.

Code Implementation

def num_submatrix_sum_target(matrix, target):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    # Create a prefix sum matrix.
    prefix_sum_matrix = [[0] * (number_of_columns + 1) for _ in range(number_of_rows + 1)]
    for row_index in range(1, number_of_rows + 1):
        for column_index in range(1, number_of_columns + 1):
            prefix_sum_matrix[row_index][column_index] = prefix_sum_matrix[row_index - 1][column_index] +\
                                        prefix_sum_matrix[row_index][column_index - 1] -\
                                        prefix_sum_matrix[row_index - 1][column_index - 1] +\
                                        matrix[row_index-1][column_index-1]

    count = 0
    # Iterate through all possible top and bottom rows.
    for top_row_index in range(1, number_of_rows + 1):
        for bottom_row_index in range(top_row_index, number_of_rows + 1):
            
            # Calculate submatrix sums and count.
            for left_column_index in range(1, number_of_columns + 1):
                for right_column_index in range(left_column_index, number_of_columns + 1):
                    
                    # Use prefix sums to calculate submatrix sum.
                    submatrix_sum = prefix_sum_matrix[bottom_row_index][right_column_index] -\
                                      prefix_sum_matrix[top_row_index - 1][right_column_index] -\
                                      prefix_sum_matrix[bottom_row_index][left_column_index - 1] +\
                                      prefix_sum_matrix[top_row_index - 1][left_column_index - 1]
                    
                    # Increment count if submatrix sum equals target.
                    if submatrix_sum == target:
                        count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0 immediately as there are no submatrices to consider.
Matrix with only one row or one column	The algorithm should still function correctly, effectively reducing to a 1D prefix sum problem.
Large matrix dimensions (potential for memory issues)	The solution must be efficient in space and time complexity to avoid memory limits exceeded errors.
Matrix containing all zeros	The code must correctly count submatrices that sum to zero if the target is also zero.
Matrix with all negative numbers and a positive target	The code must return 0 since no submatrix can sum to a positive value.
Target value is extremely large, potentially causing integer overflow during sums	Use appropriate data types (long) to prevent potential integer overflows during submatrix sum calculations.
Target is zero and matrix contains both positive and negative numbers.	The solution should accurately count submatrices summing to zero considering both positive and negative values.
No submatrix sums to the target value	The algorithm should correctly return 0 when no matching submatrix is found.

Null or empty matrix

How to Handle:

Return 0 immediately as there are no submatrices to consider.

Matrix with only one row or one column

How to Handle:

The algorithm should still function correctly, effectively reducing to a 1D prefix sum problem.

Large matrix dimensions (potential for memory issues)

How to Handle:

The solution must be efficient in space and time complexity to avoid memory limits exceeded errors.

Matrix containing all zeros

How to Handle:

The code must correctly count submatrices that sum to zero if the target is also zero.

Matrix with all negative numbers and a positive target

How to Handle:

The code must return 0 since no submatrix can sum to a positive value.

Target value is extremely large, potentially causing integer overflow during sums

How to Handle:

Use appropriate data types (long) to prevent potential integer overflows during submatrix sum calculations.

Target is zero and matrix contains both positive and negative numbers.

How to Handle:

The solution should accurately count submatrices summing to zero considering both positive and negative values.

No submatrix sums to the target value

How to Handle:

The algorithm should correctly return 0 when no matching submatrix is found.