Generate a matrix having each element equal to the sum of specified submatrices of a given matrix

0 0 16 minutes read

Given a matrix mat[][] of dimensions M*N and an integer K, the task is to generate a matrix answer[][], where answer[i][j] is equal to the sum of all elements mat[r] such that r ∈ [i – K, i + K], c ∈ [j – K, j + K], and (r, c) is a valid position in the matrix.

Examples:

Input: mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, K = 1
Output: {{12, 21, 16}, {27, 45, 33}, {24, 39, 28}}
Explanation:
answer[0][0] = mat[0][0] + mat[0][1] + mat[1][0] + mat[1][1] =1 + 2 + 4 + 5 = 12.
answer[0][1] = mat[0][0] + mat[0][1] + mat[0][2] + mat[1][0] + mat[1][1] + mat[1][2] = 1 + 2 + 3 + 4 + 5 + 6 = 21.
Similarly, answer[0][2] = 16, answer[1][0] = 27, answer[1][1] = 45, answer[1][2] = 33, answer[2][0] = 24, answer[2][1] = 39, answer[2][2] = 28

Input: mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, K = 2
Output: {{45, 45, 45}, {45, 45, 45}, {45, 45, 45}}

Naive Approach: The simplest approach is to iterate over the matrix elements using two nested loops and calculate the sum of all the elements mat[r] ( i – K ≤ r ≤ i + K, j – K ≤ c ≤ j+K ), for every possible answer[i][j]. Finally, print the matrix after traversing the matrix.

Time Complexity: O(N⁴)
Auxiliary Space: O(1)

Prefix Sum based Approach: To optimize the above approach, the idea is to initialize an auxiliary matrix aux[M][N] to store the prefix sum of all the rows of the matrix mat[][]. Once aux[][] is constructed, answer[i][j] can be calculated by traversing all rows in the range [i – K ≤ r ≤ i + K] and adding aux[r][max_col] – aux[r][min_col] + aux[r][min_col] to it. This value added denotes the sum contributed by row[r] to answer[i][j].

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required matrix
void matrixBlockSum(vector<vector<int>> mat,int K)
{
 
    // Stores number of rows and columns
    int n = mat.size();
    int m = mat[0].size();
    vector<vector<int>> mat1(n, vector<int>(m));
 
    // Traverse the matrix mat[][]
    // row-wise to calculate prefix row sum
    int cnt = 1;
    for (int i = 0; i < n; i++)
    {
        int k = 0;
        for (int j = 0; j < m; j++)
        {
 
            // Calculate Prefix Sum
            k += mat[i][j];
            mat1[i][j] = k;
            mat[i][j] = cnt;
            cnt += 1;
          }
      }
 
    // Declare the final matrix
    vector<vector<int>> ans;
 
    // Traverse the matrix row-wise
    // and fill valid indices ans[i][j]
    for (int i = 0; i < n; i++)
    {
 
        // Stores required sum of block
        // for each cell in current row
        vector<int> temp;
        for (int j = 0; j < m; j++)
        {
 
            // Fix the bounds
            // i-k >=0 and i+k < n
            // j-k > =0 and j+k < m
            int mnr = max(0, i - K);
            int mnc = max(0, j - K);
            int mxr = min(n - 1, i + K);
            int mxc = min(m - 1, j + K);
            int ans1 = 0;
 
            // Iterate in range [minimum row(mnr),
            // maximum row(mxr)] and store the sum of row k
            for (int k = mnr; k <= mxr; k++)
                ans1 += (mat1[k][mxc] - mat1[k][mnc]) + mat[k][mnc];
 
            // Append it to temp
            temp.push_back(ans1);
          }
 
        // Append temp to final matrix
        ans.push_back(temp);
      }
 
    // Print the matrix
    int xx = ans.size(), y = 0;
    cout << "[";
    for(auto i:ans)
    {
      cout << "[";
      y++;
      int x = i.size();
      for(int j = 0; j < x - 1; j++) 
        cout << i[j] << ", ";
      cout << i[x - 1] << "]";
      if(y < xx) cout << ", ";
    }
    cout << "] ";
}
 
// Driver Code
int main()
{
  vector<vector<int>> mat = { {1, 2, 3}, 
                             {4, 5, 6}, 
                             {7, 8, 9}};
  int K = 1;
  matrixBlockSum(mat, K);
  return 0;
}
 
// This code is contributed by mohit kumar 29.

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG 
{
 
  // Function to find the required matrix
  static void matrixBlockSum(int mat[][], int K)
  {
 
    // Stores number of rows and columns
    int n = mat.length;
    int m = mat[0].length;
    int mat1[][] = new int[n][m];
 
    // Traverse the matrix mat[][]
    // row-wise to calculate prefix row sum
    int cnt = 1;
    for (int i = 0; i < n; i++)
    {
      int k = 0;
      for (int j = 0; j < m; j++) 
      {
 
        // Calculate Prefix Sum
        k += mat[i][j];
        mat1[i][j] = k;
        mat[i][j] = cnt;
        cnt += 1;
      }
    }
 
    // Declare the final matrix
    int ans[][] = new int[n][m];
 
    // Traverse the matrix row-wise
    // and fill valid indices ans[i][j]
    for (int i = 0; i < n; i++)
    {
 
      // Stores required sum of block
      // for each cell in current row
      // int temp = new int[m];
      for (int j = 0; j < m; j++)
      {
 
        // Fix the bounds
        // i-k >=0 and i+k < n
        // j-k > =0 and j+k < m
        int mnr = Math.max(0, i - K);
        int mnc = Math.max(0, j - K);
        int mxr = Math.min(n - 1, i + K);
        int mxc = Math.min(m - 1, j + K);
        int ans1 = 0;
 
        // Iterate in range [minimum row(mnr),
        // maximum row(mxr)] and store the sum of
        // row k
        for (int k = mnr; k <= mxr; k++)
          ans1 += (mat1[k][mxc] - mat1[k][mnc])
          + mat[k][mnc];
 
        // Append temp to final matrix
        ans[i][j] = (ans1);
      }
    }
 
    // Print the matrix
    int xx = ans.length, y = 0;
    System.out.print("[");
    for (int i = 0; i < n; i++) 
    {
      System.out.print("[");
      y++;
      for (int j = 0; j < m - 1; j++)
        System.out.print(ans[i][j] + ", ");
      System.out.print(ans[i][m - 1] + "]");
      if (y < xx)
        System.out.print(", ");
    }
    System.out.print("] ");
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int mat[][]
      = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
    int K = 1;
    matrixBlockSum(mat, K);
  }
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python3 program for the above approach
 
# Function to find the required matrix
 
 
def matrixBlockSum(mat, K):
 
    # Stores number of rows and columns
    n = len(mat)
    m = len(mat[0])
 
    # Traverse the matrix mat[][]
    # row-wise to calculate prefix row sum
    for i in range(n):
        k = 0
        for j in range(m):
 
            # Calculate Prefix Sum
            k += mat[i][j]
            mat[i][j] = (mat[i][j], k)
 
    # Declare the final matrix
    ans = []
 
    # Traverse the matrix row-wise
    # and fill valid indices ans[i][j]
    for i in range(n):
 
        # Stores required sum of block
        # for each cell in current row
        temp = []
        for j in range(m):
 
            # Fix the bounds
            # i-k >=0 and i+k < n
            # j-k > =0 and j+k < m
            mnr = max(0, i - K)
            mnc = max(0, j - K)
            mxr = min(n - 1, i + K)
            mxc = min(m - 1, j + K)
            ans1 = 0
 
            # Iterate in range [minimum row(mnr),
            # maximum row(mxr)] and store the sum of row k
            #print(mnr,mxr+1)
            for k in range(mnr, mxr+1):
                ans1 += (mat[k][mxc][1]-mat[k][mnc][1])+mat[k][mnc][0]
 
            # Append it to temp
            temp.append(ans1)
 
        # Append temp to final matrix
        ans.append(temp)
 
    # Print the matrix
    print(ans)
 
 
# Driver Code
if __name__ == "__main__":
 
    mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    K = 1
    matrixBlockSum(mat, K)

C#

// C# program for the above approach
using System;
public class GFG 
{
 
  // Function to find the required matrix
  static void matrixBlockSum(int [,]mat, int K)
  {
 
    // Stores number of rows and columns
    int n = mat.GetLength(0);
    int m = mat.GetLength(1);
    int [,]mat1 = new int[n,m];
 
    // Traverse the matrix [,]mat
    // row-wise to calculate prefix row sum
    int cnt = 1;
    for (int i = 0; i < n; i++)
    {
      int k = 0;
      for (int j = 0; j < m; j++) 
      {
 
        // Calculate Prefix Sum
        k += mat[i,j];
        mat1[i,j] = k;
        mat[i,j] = cnt;
        cnt += 1;
      }
    }
 
    // Declare the readonly matrix
    int [,]ans = new int[n,m];
 
    // Traverse the matrix row-wise
    // and fill valid indices ans[i,j]
    for (int i = 0; i < n; i++)
    {
 
      // Stores required sum of block
      // for each cell in current row
      // int temp = new int[m];
      for (int j = 0; j < m; j++)
      {
 
        // Fix the bounds
        // i-k >=0 and i+k < n
        // j-k > =0 and j+k < m
        int mnr = Math.Max(0, i - K);
        int mnc = Math.Max(0, j - K);
        int mxr = Math.Min(n - 1, i + K);
        int mxc = Math.Min(m - 1, j + K);
        int ans1 = 0;
 
        // Iterate in range [minimum row(mnr),
        // maximum row(mxr)] and store the sum of
        // row k
        for (int k = mnr; k <= mxr; k++)
          ans1 += (mat1[k, mxc] - mat1[k, mnc])
          + mat[k, mnc];
 
        // Append temp to readonly matrix
        ans[i, j] = (ans1);
      }
    }
 
    // Print the matrix
    int xx = ans.Length, y = 0;
    Console.Write("[");
    for (int i = 0; i < n; i++) 
    {
      Console.Write("[");
      y++;
      for (int j = 0; j < m - 1; j++)
        Console.Write(ans[i, j] + ", ");
      Console.Write(ans[i, m - 1] + "]");
      if (y < xx)
        Console.Write(", ");
    }
    Console.Write("] ");
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int [,]mat
      = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
    int K = 1;
    matrixBlockSum(mat, K);
  }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the required matrix
function matrixBlockSum(mat, k)
{
     
    // Stores number of rows and columns
    let n = mat.length;
    let m = mat[0].length;
    let mat1 = new Array(n);
    for(let i = 0; i < n; i++)
    {
        mat1[i] = new Array(m);
    }
 
    // Traverse the matrix mat[][]
    // row-wise to calculate prefix row sum
    let cnt = 1;
    for(let i = 0; i < n; i++)
    {
        let k = 0;
        for(let j = 0; j < m; j++) 
        {
             
            // Calculate Prefix Sum
            k += mat[i][j];
            mat1[i][j] = k;
            mat[i][j] = cnt;
            cnt += 1;
        }
    }
 
    // Declare the final matrix
    let ans = new Array(n);
    for(let i = 0; i < n; i++)
    {
        ans[i] = new Array(m);
    }
     
    // Traverse the matrix row-wise
    // and fill valid indices ans[i][j]
    for(let i = 0; i < n; i++)
    {
         
        // Stores required sum of block
        // for each cell in current row
        // int temp = new int[m];
        for(let j = 0; j < m; j++)
        {
             
            // Fix the bounds
            // i-k >=0 and i+k < n
            // j-k > =0 and j+k < m
            let mnr = Math.max(0, i - K);
            let mnc = Math.max(0, j - K);
            let mxr = Math.min(n - 1, i + K);
            let mxc = Math.min(m - 1, j + K);
            let ans1 = 0;
             
            // Iterate in range [minimum row(mnr),
            // maximum row(mxr)] and store the sum of
            // row k
            for (let k = mnr; k <= mxr; k++)
            ans1 += (mat1[k][mxc] - mat1[k][mnc]) + 
                      mat[k][mnc];
             
            // Append temp to final matrix
            ans[i][j] = (ans1);
        }
    }
 
    // Print the matrix
    let xx = ans.length, y = 0;
    document.write("[");
    for(let i = 0; i < n; i++) 
    {
        document.write("[");
        y++;
        for (let j = 0; j < m - 1; j++)
            document.write(ans[i][j] + ", ");
             
        document.write(ans[i][m - 1] + "]");
         
        if (y < xx)
            document.write(", ");
    }
    document.write("] ");
}
 
// Driver Code
let mat = [ [ 1, 2, 3 ], 
            [ 4, 5, 6 ], 
            [ 7, 8, 9 ] ];
let K = 1;
 
matrixBlockSum(mat, K);
 
// This code is contributed by unknown2108
 
</script>

Output:

[[12, 21, 16], [27, 45, 33], [24, 39, 28]]

Time Complexity: O(N³)
Auxiliary Space: O(N²)

Efficient Approach: To optimize the above approach, the idea is to initialize an auxiliary matrix aux[M][N] such that aux[i][j] stores the sum of elements in the submatrix mat[0][0] to mat[i][j] using the following expression:

Sum of the submatrix between indices (mnr, mnc) and (mxr, mxc) is given by:
aux[mxr][mxc] – aux[mnr – 1][mxc] – aux[mxr][mnc – 1] + aux[mnr – 1][mnc – 1]
Note: The submatrix aux[mnr-1][mnc-1] is added because elements of it are subtracted twice.

Follow the steps below to construct the aux matrix:

Copy first row of mat[][] to aux[][].
Find column-wise sum of the matrix and store it.
Find the row-wise sum of updated matrix aux[][].
After the above steps, print the matrix aux[][] generated.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <iostream>
using namespace std;
 
const int M = 3; 
const int N = 3;
 
// Function to generate the required matrix
void matrixBlockSum(int mat[][M], int K)
{
     
    // Stores count of rows and columns
    int n = N;
    int m = M;
     
    // Traverse the matrix to
    // to compute prefix sum
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if (i - 1 >= 0)
            {
                mat[i][j] += mat[i - 1][j];
            }
            if (j - 1 >= 0)
            {
                mat[i][j] += mat[i][j - 1];
            }
            if (i - 1 >= 0 && j - 1 >= 0)
            {
                mat[i][j] -= mat[i - 1][j - 1];
            }
        }
    }
     
    int ans[n][m];
     
    // Traverse the matrix row-wise
    // to fill the required matrix
    for(int i = 0; i < n; i++) 
    {
        for(int j = 0; j < m; j++) 
        {
         
            // Fix the boundaries
            // i-k >=0 and i+k < n
            // j-k > =0 and j+k < m
            int mnr = max(0, i - K);
            int mxr = min(i + K, n - 1);
            int mnc = max(0, j - K);
            int mxc = min(j + K, m - 1);
             
            // Add sum of elements between
            // (0, 0) and (mxr, mxc)
            ans[i][j] = mat[mxr][mxc];
             
            // Remove elements between
            // (0, 0) and (mnr-1, mxc)
            if (mnr - 1 >= 0)
            {
                ans[i][j] -= mat[mnr - 1][mxc];
            }
             
            // Remove elements between
            // (0, 0) and (mxr, mnc-1)
            if (mnc - 1 >= 0)
            {
                ans[i][j] -= mat[mxr][mnc - 1];
            }
             
            // Add aux[mnr-1][mnc-1] as
            // elements between (0, 0)
            // and (mnr-1, mnc-1) are
            // subtracted twice
            if (mnr - 1 >= 0 && mnc - 1 >= 0)
            {
                ans[i][j] += mat[mnr - 1][mnc - 1];
            }
        }
    }
     
    // Print the matrix  
    for(int i = 0; i < n; i++)
    {        
        for(int j = 0; j < m; j++)
        {
            cout << ans[i][j] << " ";
        }
    }
}
 
// Driver code
int main() 
{
    int mat[][M] = { { 1, 2, 3 }, 
                     { 4, 5, 6 }, 
                     { 7, 8, 9 } };
    int K = 1;
     
    matrixBlockSum(mat, K);
}
 
// This code is contributed by rag2127

Java

// Java program for the above approach
import java.io.*;
 
class GFG 
{
 
  // Function to generate the required matrix
  static void matrixBlockSum(int[][] mat, int K)
  {
 
    // Stores count of rows and columns
    int n = mat.length;
    int m = mat[0].length;
 
    // Traverse the matrix to
    // to compute prefix sum
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        if (i - 1 >= 0)
        {
          mat[i][j] += mat[i - 1][j];
        }
        if (j - 1 >= 0)
        {
          mat[i][j] += mat[i][j - 1];
        }
        if (i - 1 >= 0 && j - 1 >= 0)
        {
          mat[i][j] -= mat[i - 1][j - 1];
        }
      }
    }
 
    int[][] ans = new int[n][m];
 
    // Traverse the matrix row-wise
    // to fill the required matrix
    for (int i = 0; i < n; i++) 
    {
      for (int j = 0; j < m; j++) 
      {
 
        // Fix the boundaries
        // i-k >=0 and i+k < n
        // j-k > =0 and j+k < m
        int mnr = Math.max(0, i - K);
        int mxr = Math.min(i + K, n - 1);
        int mnc = Math.max(0, j - K);
        int mxc = Math.min(j + K, m - 1);
 
        // Add sum of elements between
        // (0, 0) and (mxr, mxc)
        ans[i][j] = mat[mxr][mxc];
 
        // Remove elements between
        // (0, 0) and (mnr-1, mxc)
        if (mnr - 1 >= 0)
        {
          ans[i][j] -= mat[mnr - 1][mxc];
        }
 
        // Remove elements between
        // (0, 0) and (mxr, mnc-1)
        if (mnc - 1 >= 0)
        {
          ans[i][j] -= mat[mxr][mnc - 1];
        }
 
        // Add aux[mnr-1][mnc-1] as
        // elements between (0, 0)
        // and (mnr-1, mnc-1) are
        // subtracted twice
        if (mnr - 1 >= 0 && mnc - 1 >= 0)
        {
          ans[i][j] += mat[mnr - 1][mnc - 1];
        }
      }
    }
 
    // Print the matrix  
    for (int i = 0; i < n; i++)
    {        
      for (int j = 0; j < m; j++)
      {
        System.out.print(ans[i][j] + " ");
      }
    }
  }
 
  // Driver code
  public static void main (String[] args)
  {
    int[][] mat = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
    int K = 1;
    matrixBlockSum(mat, K);
  }
}
 
// This code is contributed by avanitrachhadiya2155.

Python3

# Python3 program for the above approach
 
# Function to generate the required matrix
 
 
def matrixBlockSum(mat, K):
 
        # Stores count of rows and columns
    n = len(mat)
    m = len(mat[0])
 
    # Traverse the matrix to
    # to compute prefix sum
    for i in range(n):
 
        for j in range(m):
 
            if i-1 >= 0:
                mat[i][j] += mat[i-1][j]
            if j-1 >= 0:
                mat[i][j] += mat[i][j-1]
            if i-1 >= 0 and j-1 >= 0:
                mat[i][j] -= mat[i-1][j-1]
 
    ans = [[0 for i in range(m)]for i in range(n)]
 
    # Traverse the matrix row-wise
    # to fill the required matrix
    for i in range(n):
        for j in range(m):
 
            # Fix the boundaries
            # i-k >=0 and i+k < n
            # j-k > =0 and j+k < m
            mnr = max(0, i - K)
            mxr = min(i + K, n-1)
            mnc = max(0, j - K)
            mxc = min(j + K, m-1)
 
            # Add sum of elements between
            # (0, 0) and (mxr, mxc)
            ans[i][j] = mat[mxr][mxc]
 
            # Remove elements between
            # (0, 0) and (mnr-1, mxc)
            if mnr - 1 >= 0:
                ans[i][j] -= mat[mnr-1][mxc]
 
            # Remove elements between
            # (0, 0) and (mxr, mnc-1)
            if mnc - 1 >= 0:
                ans[i][j] -= mat[mxr][mnc-1]
 
            # Add aux[mnr-1][mnc-1] as
            # elements between (0, 0)
                # and (mnr-1, mnc-1) are
            # subtracted twice
            if mnr - 1 >= 0 and mnc - 1 >= 0:
                ans[i][j] += mat[mnr - 1][mnc - 1]
 
    # Print the matrix
    print(ans)
 
 
# Driver Code
if __name__ == "__main__":
 
    mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
 
    K = 1
 
    matrixBlockSum(mat, K)

C#

// C# program for the above approach
using System;
class GFG 
{
 
  // Function to generate the required matrix
  static void matrixBlockSum(int[, ] mat, int K)
  {
 
    // Stores count of rows and columns
    int n = mat.GetLength(0);
    int m = mat.GetLength(1);
 
    // Traverse the matrix to
    // to compute prefix sum
    for (int i = 0; i < n; i++)
    {
 
      for (int j = 0; j < m; j++)
      {
 
        if (i - 1 >= 0)
          mat[i, j] += mat[i - 1, j];
        if (j - 1 >= 0)
          mat[i, j] += mat[i, j - 1];
        if (i - 1 >= 0 && j - 1 >= 0)
          mat[i, j] -= mat[i - 1, j - 1];
      }
    }
 
    int[, ] ans = new int[n, m];
 
    // Traverse the matrix row-wise
    // to fill the required matrix
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
 
        // Fix the boundaries
        // i-k >=0 and i+k < n
        // j-k > =0 and j+k < m
        int mnr = Math.Max(0, i - K);
        int mxr = Math.Min(i + K, n - 1);
        int mnc = Math.Max(0, j - K);
        int mxc = Math.Min(j + K, m - 1);
 
        // Add sum of elements between
        // (0, 0) and (mxr, mxc)
        ans[i, j] = mat[mxr, mxc];
 
        // Remove elements between
        // (0, 0) and (mnr-1, mxc)
        if (mnr - 1 >= 0)
          ans[i, j] -= mat[mnr - 1, mxc];
 
        // Remove elements between
        // (0, 0) and (mxr, mnc-1)
        if (mnc - 1 >= 0)
          ans[i, j] -= mat[mxr, mnc - 1];
 
        // Add aux[mnr-1][mnc-1] as
        // elements between (0, 0)
        // and (mnr-1, mnc-1) are
        // subtracted twice
        if (mnr - 1 >= 0 && mnc - 1 >= 0)
          ans[i, j] += mat[mnr - 1, mnc - 1];
      }
    }
 
    // Print the matrix
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        Console.Write(ans[i, j] + " ");
  }
 
  // Driver Code
  public static void Main()
  {
 
    int[, ] mat
      = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
    int K = 1;
    matrixBlockSum(mat, K);
  }
}
 
// This code is contributed by chitranayal.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to generate the required matrix
function matrixBlockSum(mat,K)
{
    // Stores count of rows and columns
    let n = mat.length;
    let m = mat[0].length;
  
    // Traverse the matrix to
    // to compute prefix sum
    for (let i = 0; i < n; i++)
    {
      for (let j = 0; j < m; j++)
      {
        if (i - 1 >= 0)
        {
          mat[i][j] += mat[i - 1][j];
        }
        if (j - 1 >= 0)
        {
          mat[i][j] += mat[i][j - 1];
        }
        if (i - 1 >= 0 && j - 1 >= 0)
        {
          mat[i][j] -= mat[i - 1][j - 1];
        }
      }
    }
  
    let ans = new Array(n);
    for(let i=0;i<n;i++)
    {
        ans[i]=new Array(m);
        for(let j=0;j<m;j++)
            ans[i][j]=0;
    }
  
    // Traverse the matrix row-wise
    // to fill the required matrix
    for (let i = 0; i < n; i++)
    {
      for (let j = 0; j < m; j++)
      {
  
        // Fix the boundaries
        // i-k >=0 and i+k < n
        // j-k > =0 and j+k < m
        let mnr = Math.max(0, i - K);
        let mxr = Math.min(i + K, n - 1);
        let mnc = Math.max(0, j - K);
        let mxc = Math.min(j + K, m - 1);
  
        // Add sum of elements between
        // (0, 0) and (mxr, mxc)
        ans[i][j] = mat[mxr][mxc];
  
        // Remove elements between
        // (0, 0) and (mnr-1, mxc)
        if (mnr - 1 >= 0)
        {
          ans[i][j] -= mat[mnr - 1][mxc];
        }
  
        // Remove elements between
        // (0, 0) and (mxr, mnc-1)
        if (mnc - 1 >= 0)
        {
          ans[i][j] -= mat[mxr][mnc - 1];
        }
  
        // Add aux[mnr-1][mnc-1] as
        // elements between (0, 0)
        // and (mnr-1, mnc-1) are
        // subtracted twice
        if (mnr - 1 >= 0 && mnc - 1 >= 0)
        {
          ans[i][j] += mat[mnr - 1][mnc - 1];
        }
      }
    }
  
    // Print the matrix 
    for (let i = 0; i < n; i++)
    {       
      for (let j = 0; j < m; j++)
      {
        document.write(ans[i][j] + " ");
      }
    }
}
 
 // Driver code
let mat=[[ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]];
let K = 1;
matrixBlockSum(mat, K);
 
 
// This code is contributed by patel2127
 
</script>

Output:

[[12, 21, 16], [27, 45, 33], [24, 39, 28]]

Time Complexity: O(N²)
Auxiliary Space: O(N²)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!