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] = 28Input: 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(N4)
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 matrixvoid 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 Codeint 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 approachimport 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 matrixdef 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 Codeif __name__ == "__main__": mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] K = 1 matrixBlockSum(mat, K) |
C#
// C# program for the above approachusing 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 matrixfunction 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 Codelet 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(N3)
Auxiliary Space: O(N2)
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 matrixvoid 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 codeint 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 approachimport 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 matrixdef 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 Codeif __name__ == "__main__": mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] K = 1 matrixBlockSum(mat, K) |
C#
// C# program for the above approachusing 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 matrixfunction 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 codelet 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(N2)
Auxiliary Space: O(N2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
