Matrix Block Sum - Leetcode Solution

Problem statement: Given a m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - k <= r <= i + k, j - k <= c <= j + k, and (r, c) is a valid position in the matrix.

Example: Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1 Output: [[12,21,16],[27,45,33],[24,39,28]]

Solution:

To solve this problem, we will use dynamic programming approach. We will first create a cumulative sum matrix that will contain the sum of all elements in the matrix upto that cell. Then, we will use this cumulative sum matrix to compute the desired sum.

1. Create a cumulative sum matrix:

   • Initialize a new matrix called sum_mat with the same dimensions as the given matrix mat.
   • For all cells (i, j) in the sum_mat matrix, set the sum as follows: sum_mat[i][j] = mat[i][j] + sum_mat[i-1][j] + sum_mat[i][j-1] - sum_mat[i-1][j-1], where the first term in the right is the current value in mat, and the remaining three terms are the cumulative sum upto that cell.

2. Compute the desired sum:

   • Initialize a new matrix called answer with the same dimensions as the given matrix mat.
   • For all cells (i, j) in the answer matrix, set the sum as follows: answer[i][j] = sum_mat[min(i+k, m-1)][min(j+k, n-1)] - sum_mat[max(i-k-1, 0)][min(j+k, n-1)] - sum_mat[min(i+k, m-1)][max(j-k-1, 0)] + sum_mat[max(i-k-1, 0)][max(j-k-1, 0)], where m and n are the number of rows and columns in the mat matrix respectively. This sum is computed by using the cumulative sum matrix to find the sum of all elements in the sub-matrix (i-k, j-k) to (i+k, j+k) including the bounds. However, we need to subtract the sum of elements outside this sub-matrix, which can be computed using the cumulative sum matrix.

3. Return the answer matrix.

Implementation:

class Solution { public: vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) { int m = mat.size(), n = mat[0].size(); vector<vector<int>> sum_mat(m, vector<int>(n, 0)); vector<vector<int>> answer(m, vector<int>(n, 0));

    // create the cumulative sum matrix
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            sum_mat[i][j] = mat[i][j];
            if(i > 0) sum_mat[i][j] += sum_mat[i-1][j];
            if(j > 0) sum_mat[i][j] += sum_mat[i][j-1];
            if(i > 0 && j > 0) sum_mat[i][j] -= sum_mat[i-1][j-1];
        }
    }

    // compute the desired sum
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            answer[i][j] = sum_mat[min(i+k, m-1)][min(j+k, n-1)];
            if(i-k-1 >= 0) answer[i][j] -= sum_mat[i-k-1][min(j+k, n-1)];
            if(j-k-1 >= 0) answer[i][j] -= sum_mat[min(i+k, m-1)][j-k-1];
            if(i-k-1 >= 0 && j-k-1 >= 0) answer[i][j] += sum_mat[i-k-1][j-k-1];
        }
    }

    return answer;
}

};

Time Complexity: O(mn), where m and n are the number of rows and columns in the mat matrix respectively. Space Complexity: O(mn), for the sum_mat and answer matrices.

1