Matrix Block Sum

Medium

Matrix Block Sum

Medium

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)? Are they likely to be very large?
What is the range of values within the matrix? Can the matrix contain negative numbers, zero, or only positive integers?
What is the range of the value 'k'? Can 'k' be zero or negative?
How should I handle cases where the block defined by 'k' extends beyond the boundaries of the matrix? Should I assume values outside the boundary are zero?
Is the input matrix guaranteed to be rectangular (i.e., all rows have the same number of columns)? What should I return if the input is invalid (e.g., null or empty matrix)?

Brute Force Solution

Approach

For each position in the matrix, we need to find the sum of the numbers in a surrounding block. The brute force approach calculates this sum individually for every single position by directly adding up the numbers within the block.

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

For each position in the matrix, imagine a square block of numbers centered around that position.
For each block, go through each number inside the block and add it to a running total.
After adding all numbers in the block, record the total sum for that central position.
Repeat this process of selecting a position, forming a block, and summing the numbers for every position in the matrix.

Code Implementation

def matrix_block_sum_brute_force(matrix, k_size):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    block_sum_matrix = [[0] * number_of_columns for _ in range(number_of_rows)]

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            # Need to calculate block sum for current position.
            block_sum = 0

            for block_row in range(max(0, row_index - k_size), min(number_of_rows, row_index + k_size + 1)):
                # We must iterate across the rows in the block around current position
                for block_column in range(max(0, column_index - k_size), min(number_of_columns, column_index + k_size + 1)):
                    # We must also iterate across columns in block.
                    block_sum += matrix[block_row][block_column]

            # Store sum in result matrix.
            block_sum_matrix[row_index][column_index] = block_sum

    return block_sum_matrix

Big(O) Analysis

Time Complexity

O(m*n*k*k) – Let m be the number of rows and n be the number of columns in the matrix. For each of the m*n cells in the matrix, we are calculating the sum of a block of size k*k, where k is related to the given parameter K (block radius). Therefore, for each cell, we iterate over the k rows above and below and the k columns to the left and right. This leads to m*n cells each requiring O(k*k) computation. So, the total time complexity is O(m*n*k*k).

Space Complexity

O(1) – The brute force approach calculates the block sum directly without using any auxiliary data structures like arrays, lists, or hashmaps to store intermediate results. It only uses a few variables to keep track of the row and column indices during the iteration through the matrix and to accumulate the sum within each block. The amount of extra memory used does not scale with the input matrix size (number of rows and columns). Therefore, the space complexity is constant.

Optimal Solution

Approach

The trick to solving this problem efficiently is to precompute the sum of every rectangular sub-region of the matrix. Then, for each query, you can quickly calculate the block sum using these precomputed values, instead of recalculating the sum each time. This avoids redundant calculations and significantly speeds things up.

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

First, create a new matrix that stores the cumulative sum of the original matrix. Each cell in this new matrix will hold the sum of all the elements in the original matrix from the top-left corner up to that cell.
To fill the cumulative sum matrix, start from the top-left corner. The first cell is the same as the original matrix.
For any other cell, its value is the sum of the current cell in the original matrix, plus the cell above it in the cumulative sum matrix, plus the cell to its left, minus the cell diagonally above and to the left (to avoid double-counting).
Once you have the cumulative sum matrix, you can quickly calculate the block sum for any given region.
To find the block sum, use the coordinates of the top-left and bottom-right corners of the block, based on the given center cell and radius.
Look up the corresponding cells in the cumulative sum matrix.
The block sum is calculated by adding the value at the bottom-right corner, subtracting the value to the left of the top-left corner and above the bottom-right corner and adding back the value to the left and above of top-left corner (inclusion-exclusion principle). This gives you the sum of all the elements within the block.
Repeat this process for each center cell to get the final result matrix.

Code Implementation

def matrix_block_sum(matrix, radius):
    rows = len(matrix)
    cols = len(matrix[0])

    # cumulative_sum_matrix[i][j] is sum of matrix[0...i-1][0...j-1]
    cumulative_sum_matrix = [[0] * (cols + 1) for _ in range(rows + 1)]

    for row_index in range(1, rows + 1):
        for col_index in range(1, cols + 1):
            cumulative_sum_matrix[row_index][col_index] = matrix[row_index - 1][col_index - 1] + \
                cumulative_sum_matrix[row_index - 1][col_index] + \
                cumulative_sum_matrix[row_index][col_index - 1] - \
                cumulative_sum_matrix[row_index - 1][col_index - 1]

    result_matrix = [[0] * cols for _ in range(rows)]

    for row_index in range(rows):
        for col_index in range(cols):
            row_start = max(0, row_index - radius)
            col_start = max(0, col_index - radius)
            row_end = min(rows, row_index + radius + 1)
            col_end = min(cols, col_index + radius + 1)

            # Applying inclusion-exclusion principle
            result_matrix[row_index][col_index] = cumulative_sum_matrix[row_end][col_end] - \
                cumulative_sum_matrix[row_start][col_end] - \
                cumulative_sum_matrix[row_end][col_start] + \
                cumulative_sum_matrix[row_start][col_start]

    return result_matrix

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm first constructs a cumulative sum matrix of size m x n, where m is the number of rows and n is the number of columns in the input matrix. This construction involves iterating through each cell of the matrix once, leading to O(m*n) time complexity. After the cumulative sum matrix is built, the algorithm calculates the block sum for each cell in the original matrix. Since each block sum calculation uses only constant time lookups and arithmetic operations on the cumulative sum matrix, and this is performed for every cell in the original m x n matrix, the overall time complexity remains O(m*n). There are no nested loops that depend on input values so we end up with O(m*n) rather than O(m^2 * n^2)

Space Complexity

O(M*N) – The algorithm creates a new matrix, `cumulative_sum_matrix`, to store the cumulative sums of the original matrix. The dimensions of this matrix are the same as the input matrix, which is M rows and N columns, where M is the number of rows and N is the number of columns in the input matrix. Therefore, the space required for the `cumulative_sum_matrix` is proportional to M*N. The final result matrix will also be of size M*N, which is used to store the block sums. This dominates any constant space usage, resulting in an auxiliary space complexity of O(M*N).

Edge Cases

Case	How to Handle
Null or empty matrix	Return an empty matrix (or a matrix of the same dimensions filled with zeros) after checking for null or zero dimensions.
K is zero	The sum at each cell becomes the value of the cell itself, so return a matrix where each cell is equal to the original matrix.
K is larger than the matrix dimensions	Treat K as the maximum possible index for rows and columns, effectively summing the whole input matrix.
Matrix contains negative numbers	The prefix sum calculation handles negative numbers correctly, contributing negatively to sums.
Integer overflow in the prefix sum calculation	Use a data type like `long` to store the prefix sum to prevent integer overflow issues during accumulation and differencing.
Single element matrix	Return a matrix of the same dimension where the single element is the original element if K >= 0 or 0 if K < 0 in some problem modifications
Large matrix dimensions impacting memory	The prefix sum matrix can be optimized to in-place modification of the original matrix for reduced memory footprint but impacts the original input.
K is a very large number	Clamp K to the maximum possible row and column index for efficient processing, treating the range as the entire matrix size.