# Matrix Block Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/matrix-block-sum)
Canonical: https://scaleengineer.com/dsa/problems/matrix-block-sum
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
---
## Problem
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
## Brute Force Iteration
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Dynamic Programming with Integral Image
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        
        // Create the integral image (summed-area table)
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i + 1][j + 1] = mat[i][j] + dp[i][j + 1] + dp[i + 1][j] - dp[i][j];
            }
        }
        
        int[][] answer = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Determine the block boundaries, clamping to the matrix dimensions
                int r1 = Math.max(0, i - k);
                int c1 = Math.max(0, j - k);
                int r2 = Math.min(m - 1, i + k);
                int c2 = Math.min(n - 1, j + k);
                
                // Use the integral image to calculate the sum in O(1)
                // Note the +1 offset for dp table indices
                answer[i][j] = dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1];
            }
        }
        
        return answer;
    }
}
```
### 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`.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> matrixBlockSum(vector<vector<int>> &mat, int k) {
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> pre(m + 1, vector<int>(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];
      }
    }
    vector<vector<int>> ans(m, vector<int>(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, m, n, pre) -
                    get(i + k + 1, j - k, m, n, pre) -
                    get(i - k, j + k + 1, m, n, pre) +
                    get(i - k, j - k, m, n, pre);
      }
    }
    return ans;
  }
  int get(int i, int j, int m, int n, vector<vector<int>> &pre) {
    i = max(min(m, i), 0);
    j = max(min(n, j), 0);
    return pre[i][j];
  }
};

```

### Python

```python
class Solution:
    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

```