Matrix Block Sum

Med

#1223Time: O(m * n * k^2), where `m` and `n` are the dimensions of the matrix. For each of the `m * n` cells, we iterate over a block of size approximately `(2k+1) * (2k+1)`, leading to the complexity.Space: O(m * n) to store the output matrix `answer`. If the output matrix is not considered extra space, the complexity is O(1).

Patterns

Prefix Sum

Data structures

Array Matrix

Prompt

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 1:

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

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n, k <= 100
1 <= mat[i][j] <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. For each cell (i, j) in the output matrix, we iterate over the entire corresponding block in the input matrix, summing up the values. We must carefully handle the matrix boundaries to avoid out-of-bounds errors.

Algorithm

Initialize an m x n matrix answer.
Iterate through each cell (i, j) from (0, 0) to (m-1, n-1).
For each (i, j), initialize sum = 0.
Iterate through rows r from i - k to i + k.
Iterate through columns c from j - k to j + k.
If (r, c) is a valid index in mat, add mat[r][c] to sum.
Set answer[i][j] = sum.
Return answer.

Walkthrough

This method involves a straightforward, nested loop structure.

First, we create an m x n result matrix answer, initialized with zeros.
We then use two outer loops to iterate through each cell (i, j) of the answer matrix.
For each (i, j), we initialize a sum variable to zero. Then, we start another pair of nested loops to iterate through the block defined by the problem. The row index r will go from i - k to i + k, and the column index c will go from j - k to j + k.
Inside the innermost loop, we must check if the current cell (r, c) is within the valid bounds of the original matrix mat (i.e., 0 <= r < m and 0 <= c < n).
If (r, c) is a valid cell, we add its value mat[r][c] to our running sum.
After iterating through the entire block, the calculated sum is placed in answer[i][j].
This process is repeated for all cells (i, j) until the answer matrix is fully populated.

1class Solution {2    public int[][] matrixBlockSum(int[][] mat, int k) {3        int m = mat.length;4        int n = mat[0].length;5        int[][] answer = new int[m][n];6 7        for (int i = 0; i < m; i++) {8            for (int j = 0; j < n; j++) {9                int sum = 0;10                // Iterate through the block11                for (int r = i - k; r <= i + k; r++) {12                    for (int c = j - k; c <= j + k; c++) {13                        // Check if the cell is within the matrix bounds14                        if (r >= 0 && r < m && c >= 0 && c < n) {15                            sum += mat[r][c];16                        }17                    }18                }19                answer[i][j] = sum;20            }21        }22        return answer;23    }24}

Complexity

Time

O(m * n * k^2), where `m` and `n` are the dimensions of the matrix. For each of the `m * n` cells, we iterate over a block of size approximately `(2k+1) * (2k+1)`, leading to the complexity.

Space

O(m * n) to store the output matrix `answer`. If the output matrix is not considered extra space, the complexity is O(1).

Trade-offs

Pros

Simple to understand and implement.
Directly follows the problem definition.
Low constant factor in its complexity.

Cons

Highly inefficient due to redundant calculations.
Time complexity is dependent on k, making it slow for large k values.

This optimized approach avoids redundant calculations by pre-computing a sum-area table (also known as an integral image). This table, let's call it dp, stores the sum of all elements in the rectangle from the origin (0, 0) to every other cell (i, j). Once this table is built, the sum of any rectangular block can be calculated in constant time using the values at its four corners.

Algorithm

Create an integral image matrix dp of size (m+1) x (n+1).
Populate dp such that dp[i+1][j+1] contains the sum of the rectangle from (0,0) to (i,j) in mat.
Initialize an m x n matrix answer.
Iterate through each cell (i, j) from (0, 0) to (m-1, n-1).
For each (i, j), calculate the block boundaries: r1, c1, r2, c2.
Calculate the block sum using the dp table: sum = dp[r2+1][c2+1] - dp[r1][c2+1] - dp[r2+1][c1] + dp[r1][c1].
Set answer[i][j] = sum.
Return answer.

Walkthrough

The core idea is to first build an auxiliary matrix dp of size (m+1) x (n+1). dp[i+1][j+1] will store the sum of all elements in the rectangle of mat from (0, 0) to (i, j). The extra row and column in dp act as padding, simplifying the calculation.

Step 1: Build the Integral Image The dp table is populated using the following recurrence relation: dp[i+1][j+1] = mat[i][j] + dp[i][j+1] + dp[i+1][j] - dp[i][j] This step takes O(m * n) time.

Step 2: Calculate Block Sums After the dp table is ready, we iterate through each cell (i, j) of the original matrix to compute answer[i][j]. For each (i, j), we define the boundaries of the required block, ensuring they are within the matrix dimensions: r1 = max(0, i - k), c1 = max(0, j - k), r2 = min(m - 1, i + k), c2 = min(n - 1, j + k). The sum of this block can be found in O(1) time using the dp table: sum = dp[r2+1][c2+1] - dp[r1][c2+1] - dp[r2+1][c1] + dp[r1][c1] This sum is then assigned to answer[i][j]. This step also takes O(m * n) time.

1class Solution {2    public int[][] matrixBlockSum(int[][] mat, int k) {3        int m = mat.length;4        int n = mat[0].length;5        6        // Create the integral image (summed-area table)7        int[][] dp = new int[m + 1][n + 1];8        for (int i = 0; i < m; i++) {9            for (int j = 0; j < n; j++) {10                dp[i + 1][j + 1] = mat[i][j] + dp[i][j + 1] + dp[i + 1][j] - dp[i][j];11            }12        }13        14        int[][] answer = new int[m][n];15        for (int i = 0; i < m; i++) {16            for (int j = 0; j < n; j++) {17                // Determine the block boundaries, clamping to the matrix dimensions18                int r1 = Math.max(0, i - k);19                int c1 = Math.max(0, j - k);20                int r2 = Math.min(m - 1, i + k);21                int c2 = Math.min(n - 1, j + k);22                23                // Use the integral image to calculate the sum in O(1)24                // Note the +1 offset for dp table indices25                answer[i][j] = dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1];26            }27        }28        29        return answer;30    }31}

Complexity

Time

O(m * n). Building the integral image takes O(m * n), and filling the answer matrix also takes O(m * n). The total time is O(m * n) + O(m * n) = O(m * n).

Space

O(m * n) to store the integral image `dp` table and the output `answer` matrix.

Trade-offs

Pros

Highly efficient with a time complexity independent of k.
Avoids redundant computations by pre-calculating prefix sums.

Cons

Requires additional space for the integral image table.
The logic for calculating sums from the integral image can be slightly tricky to get right.

Solutions

Solution

1class Solution {2private3  int[][] pre;4private5  int m;6private7  int n;8public9  int[][] matrixBlockSum(int[][] mat, int k) {10    int m = mat.length, n = mat[0].length;11    int[][] pre = new int[m + 1][n + 1];12    for (int i = 1; i < m + 1; ++i) {13      for (int j = 1; j < n + 1; ++j) {14        pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + -pre[i - 1][j - 1] +15                    mat[i - 1][j - 1];16      }17    }18    this.pre = pre;19    this.m = m;20    this.n = n;21    int[][] ans = new int[m][n];22    for (int i = 0; i < m; ++i) {23      for (int j = 0; j < n; ++j) {24        ans[i][j] = get(i + k + 1, j + k + 1) - get(i + k + 1, j - k) -25                    get(i - k, j + k + 1) + get(i - k, j - k);26      }27    }28    return ans;29  }30private31  int get(int i, int j) {32    i = Math.max(Math.min(m, i), 0);33    j = Math.max(Math.min(n, j), 0);34    return pre[i][j];35  }36}

1class Solution {2public:3  vector<vector<int>> matrixBlockSum(vector<vector<int>> &mat, int k) {4    int m = mat.size(), n = mat[0].size();5    vector<vector<int>> pre(m + 1, vector<int>(n + 1));6    for (int i = 1; i < m + 1; ++i) {7      for (int j = 1; j < n + 1; ++j) {8        pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + -pre[i - 1][j - 1] +9                    mat[i - 1][j - 1];10      }11    }12    vector<vector<int>> ans(m, vector<int>(n));13    for (int i = 0; i < m; ++i) {14      for (int j = 0; j < n; ++j) {15        ans[i][j] = get(i + k + 1, j + k + 1, m, n, pre) -16                    get(i + k + 1, j - k, m, n, pre) -17                    get(i - k, j + k + 1, m, n, pre) +18                    get(i - k, j - k, m, n, pre);19      }20    }21    return ans;22  }23  int get(int i, int j, int m, int n, vector<vector<int>> &pre) {24    i = max(min(m, i), 0);25    j = max(min(n, j), 0);26    return pre[i][j];27  }28};

1class Solution:2    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]: m, n = len(mat), len(mat[0]) pre = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): pre[i][j] = (pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + mat[i - 1][j - 1]) def get(i, j): i = max(min(m, i), 0) j = max(min(n, j), 0) return pre[i][j] ans = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): ans[i][j] = (get(i + k + 1, j + k + 1) - get(i + k + 1, j - k) - get(i - k, j + k + 1) + get(i - k, j - k)) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem