Scale Engineer

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
ArrayMatrix

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.

  1. First, we create an m x n result matrix answer, initialized with zeros.
  2. We then use two outer loops to iterate through each cell (i, j) of the answer matrix.
  3. 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.
  4. 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).
  5. If (r, c) is a valid cell, we add its value mat[r][c] to our running sum.
  6. After iterating through the entire block, the calculated sum is placed in answer[i][j].
  7. This process is repeated for all cells (i, j) until the answer matrix is fully populated.
class Solution {    public int[][] matrixBlockSum(int[][] mat, int k) {        int m = mat.length;        int n = mat[0].length;        int[][] answer = new int[m][n];         for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                int sum = 0;                // Iterate through the block                for (int r = i - k; r <= i + k; r++) {                    for (int c = j - k; c <= j + k; c++) {                        // Check if the cell is within the matrix bounds                        if (r >= 0 && r < m && c >= 0 && c < n) {                            sum += mat[r][c];                        }                    }                }                answer[i][j] = sum;            }        }        return answer;    }}

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.

Solutions

class Solution {private  int[][] pre;private  int m;private  int n;public  int[][] matrixBlockSum(int[][] mat, int k) {    int m = mat.length, n = mat[0].length;    int[][] pre = new int[m + 1][n + 1];    for (int i = 1; i < m + 1; ++i) {      for (int j = 1; j < n + 1; ++j) {        pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + -pre[i - 1][j - 1] +                    mat[i - 1][j - 1];      }    }    this.pre = pre;    this.m = m;    this.n = n;    int[][] ans = new int[m][n];    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        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;  }private  int get(int i, int j) {    i = Math.max(Math.min(m, i), 0);    j = Math.max(Math.min(n, j), 0);    return pre[i][j];  }}

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 →

Next problem