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 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> |
[[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 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> |
[[12, 21, 16], [27, 45, 33], [24, 39, 28]]
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!