1314. Matrix Block Sum LeetCode Solution

In this guide, you will get 1314. Matrix Block Sum LeetCode Solution with the best time and space complexity. The solution to Matrix Block Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Matrix Block Sum solution in C++
Matrix Block Sum solution in Java
Matrix Block Sum solution in Python
Additional Resources

1314. Matrix Block Sum LeetCode Solution image

Problem Statement of Matrix Block Sum

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

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

1314. Matrix Block Sum LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
    const int m = mat.size();
    const int n = mat[0].size();
    vector<vector<int>> ans(m, vector<int>(n));
    vector<vector<int>> prefix(m + 1, vector<int>(n + 1));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        prefix[i + 1][j + 1] =
            mat[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        const int r1 = max(0, i - k) + 1;
        const int c1 = max(0, j - k) + 1;
        const int r2 = min(m - 1, i + k) + 1;
        const int c2 = min(n - 1, j + k) + 1;
        ans[i][j] = prefix[r2][c2] - prefix[r2][c1 - 1] - prefix[r1 - 1][c2] +
                    prefix[r1 - 1][c1 - 1];
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

1314. Matrix Block Sum LeetCode Solution in Java

class Solution {
  public int[][] matrixBlockSum(int[][] mat, int k) {
    final int m = mat.length;
    final int n = mat[0].length;
    int[][] ans = new int[m][n];
    int[][] prefix = new int[m + 1][n + 1];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        prefix[i + 1][j + 1] = mat[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        final int r1 = Math.max(0, i - k) + 1;
        final int c1 = Math.max(0, j - k) + 1;
        final int r2 = Math.min(m - 1, i + k) + 1;
        final int c2 = Math.min(n - 1, j + k) + 1;
        ans[i][j] =
            prefix[r2][c2] - prefix[r2][c1 - 1] - prefix[r1 - 1][c2] + prefix[r1 - 1][c1 - 1];
      }

    return ans;
  }
}
// code provided by PROGIEZ

1314. Matrix Block Sum LeetCode Solution in Python

class Solution:
  def matrixBlockSum(self, mat: list[list[int]], k: int) -> list[list[int]]:
    m = len(mat)
    n = len(mat[0])
    ans = [[0] * n for _ in range(m)]
    prefix = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m):
      for j in range(n):
        prefix[i + 1][j + 1] = (mat[i][j] + prefix[i][j + 1] +
                                prefix[i + 1][j] - prefix[i][j])

    for i in range(m):
      for j in range(n):
        r1 = max(0, i - k) + 1
        c1 = max(0, j - k) + 1
        r2 = min(m - 1, i + k) + 1
        c2 = min(n - 1, j + k) + 1
        ans[i][j] = (prefix[r2][c2] - prefix[r2][c1 - 1] -
                     prefix[r1 - 1][c2] + prefix[r1 - 1][c1 - 1])

    return ans
 # code by PROGIEZ