Leetcode 1314. Matrix Block Sum

Problem Explanation

The problem asks to return a matrix where each cell contains the sum of all neighboring cells in the given radius distance and including itself. The radius is provided as K.

For example:

1
2
3If the matrix 'mat' is:
4
51 2 3
64 5 6
77 8 9
8
9And the radius 'K' is 1, the output is:
10
1112 21 16
1227 45 33
1324 39 28

In the above example, the first cell (0,0) of the answer is '12' because the sum of the neighboring elements at a distance of 1 from (0,0) which are (0,1), (1,0), (1,1) and the cell itself (0,0) is 12.

The solution makes use of dynamic programming, specifically "prefix sum". This is a method where you precalculate the summed values of the array to provide for quick summations of any contiguous slice of the array. In a 2-Dimensional context, precise summations of specific areas of the matrix grid can be done, provided it is a rectangular region.

Solution in Java

1
2java
3class Solution {
4    public int[][] matrixBlockSum(int[][] mat, int K) {
5        int m = mat.length, n = mat[0].length;
6        int[][] prefix = new int[m + 1][n + 1], res = new int[m][n];
7        
8        for (int i = 1; i <= m; i++) {
9            for (int j = 1; j <= n; j++) {
10                prefix[i][j] = mat[i-1][j-1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
11            }
12        }
13        
14        for (int i = 0; i < m; i++) {
15            for (int j = 0; j < n; j++) {
16                int r1 = Math.max(0, i - K), c1 = Math.max(0, j - K), r2 = Math.min(m, i + K + 1), c2 = Math.min(n, j + K + 1);
17                res[i][j] = prefix[r2][c2] - prefix[r1][c2] - prefix[r2][c1] + prefix[r1][c1];
18            }
19        }
20        
21        return res;
22    }
23}

In the above Java solution, first, we prepare the prefix sum matrix. Then we calculate the sum of the submatrix by subtracting the unwanted areas from the cumulative area covered by the prefix matrix.

Solution in Python

1
2python
3class Solution:
4    def matrixBlockSum(self, mat, K):
5        m, n = len(mat), len(mat[0])
6        prefix = [[0]*(n+1) for _ in range(m+1)]
7        for i in range(m):
8            for j in range(n):
9                prefix[i+1][j+1] = mat[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]
10                
11        res = [[0]*n for _ in range(m)]
12        for i in range(m):
13            for j in range(n):
14                r1, c1 = max(0, i-K), max(0, j-K)
15                r2, c2 = min(m, i+K+1), min(n, j+K+1)
16                res[i][j] = prefix[r2][c2] - prefix[r1][c2] - prefix[r2][c1] + prefix[r1][c1]
17        return res

In the above Python solution, the prefix sum matrix is prepared. then for every cell, the sum of the neighboring cells within the distance K is calculated by using the prefix sum.

Solution in C#

1
2csharp
3public class Solution {
4    public int[][] MatrixBlockSum(int[][] mat, int K) {
5        int m = mat.Length, n = mat[0].Length;
6        int[][] prefix = new int[m + 1][], res = new int[m][];
7        for (int i = 0; i <= m; i++) prefix[i] = new int[n + 1];
8        for (int i = 0; i < m; i++) res[i] = new int[n];
9        
10        for (int i = 1; i <= m; i++)
11            for (int j = 1; j <= n; j++)
12                prefix[i][j] = mat[i-1][j-1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
13        
14        for (int i = 0; i < m; i++)
15            for (int j = 0; j < n; j++) {
16                int r1 = Math.Max(0, i - K), r2 = Math.Min(m, i + K + 1), c1 = Math.Max(0, j - K), c2 = Math.Min(n, j + K + 1);
17                res[i][j] = prefix[r2][c2] - prefix[r1][c2] - prefix[r2][c1] + prefix[r1][c1];
18            }
19        
20        return res;
21    }
22}

The above C# solution follows a very similar logic to the Java and Python solutions due to the syntactic similarity.

Solution in JavaScript

1
2javascript
3var matrixBlockSum = function(mat, K) {
4    let m = mat.length, n = mat[0].length;
5    let prefix = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
6    let res = Array.from({length: m}, () => Array(n).fill(0));
7
8    for (let i = 1; i <= m; ++i) 
9        for (let j = 1; j <= n; ++j) 
10            prefix[i][j] = mat[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
11      
12    for (let i = 0; i < m; ++i) 
13        for (let j = 0; j < n; ++j) {
14            let r1 = Math.max(0, i - K), r2 = Math.min(m, i + K + 1), c1 = Math.max(0, j - K), c2 = Math.min(n, j + K + 1);
15            res[i][j] = prefix[r2][c2] - prefix[r1][c2] - prefix[r2][c1] + prefix[r1][c1];
16        }
17    
18    return res;
19};

The JavaScript implementation uses higher-order functions to generate arrays of certain lengths. They then go for each i and j to calculate the sums and apply them to the res array that serves as the output.## Conclusion

This problem is a perfect depiction of how dynamic programming can turn an algorithm from a naive solution with quadratic or cubic complexity into an efficiently solvable problem. Provided you learn the technique well, most of these problems can become commonplace and easily solvable.

The use of prefix sum allows us to have pre-calculated cumulative sums and waste no more time in re-calculating them every time a submatrix sum is needed. The solutions provided here in various programming languages show a similar approach where first, the prefix sum matrix is prepared and then the required matrix is prepared using the prefix sum.

Whether you are dealing with simple 1D arrays or complex 2D matrices, applying dynamic programming techniques can save you a lot of computational time. Especially in problems that require frequent calculations of sums over sub-portions, prefix sum algorithm is the key to optimize your solution.

This problem along with its solutions demonstrate an interactive way to learn the prefix sum algorithm and get used to problem-solving in dynamic programming. With continued practice and understanding of such problems, you will be able to handle even more complex problems using these techniques.

Remember, dynamic programming does require some initial effort to understand, but it makes solving complex problems much easier and more efficient. Develop the habit of identifying where such techniques apply and practice using them in your coding tasks for optimal solutions.

Whether it's Java, Python, C# or JavaScript, the same logic of dynamic programming and prefix sum can be used to efficiently solve such problems.