Construct a Matrix such that each cell consists of sum of adjacent elements of respective cells in given Matrix
Given a matrix arr[][] of dimensions N * M, the task is to generate a matrix such that any cell (r, c) stores the sum of adjacent elements present horizontally, vertically, and diagonally in the given matrix.
Examples:
Input: arr[][] = {{1, 3}, {2, 4}}
Output: {{9, 7}, {8, 6}}
Explanation: Matrix is constructed by the following operations:
For cell (0, 0), arr[1][0] + arr[0][1] + arr[1][1] = 2 + 3 + 4 = 9.
For cell (0, 1), arr[1][0] + arr[0][0] + arr[1][1] = 2 + 1 + 4 = 7.
For cell (1, 0), arr[0][0] + arr[0][1] + arr[1][1] = 1 + 3 + 4 = 8.
For cell (1, 1), arr[1][0] + arr[0][1] + arr[0][0] = 2 + 3 + 1 = 6.Input: arr[][] = {{1}}
Output: {{0}}
Approach: The idea is to traverse each cell of the given matrix and for each cell (r, c), store the sum of adjacent cells {{r-1, c-1}, {r+1, c+1}, {r-1, c+1}, {r+1, c-1}, {r, c-1}, {r-1, c}, {r+1, c}, {r, c+1}} if possible.
- Initialize a matrix v[][] of dimension N * M to store the results of each cell.
- Now, traverse each cell of the matrix. For each cell, check for valid adjacent cells and keep updating their sum.
- After traversing, print the value stored in each cell of the matrix v[][].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Initialize rows and columns int r, c; // Store all 8 directions vector<vector< int > > dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 } }; // Function to check if a cell // (i, j) is valid or not bool valid( int i, int j) { if (i >= 0 && j >= 0 && i < r && j < c) return 1; return 0; } // Function to find sum of adjacent cells // for cell (i, j) int find( int i, int j, vector<vector< int > >& v) { // Initialize sum int s = 0; // Visit all 8 directions for ( auto x : dir) { int ni = i + x[0], nj = j + x[1]; // Check if cell is valid if (valid(ni, nj)) s += v[ni][nj]; } // Return sum return s; } // Function to print sum of adjacent elements void findsumofneighbors(vector<vector< int > >& M) { // Stores the resultant matrix vector<vector< int > > v(r, vector< int >(c, 0)); // Iterate each elements of matrix for ( int i = 0; i < r; i++) { for ( int j = 0; j < c; j++) { // Find adjacent sum v[i][j] = find(i, j, M); cout << v[i][j] << " " ; } cout << "\n" ; } } // Driver Code int main() { // Given matrix vector<vector< int > > M = { { 1, 4, 1 }, { 2, 4, 5 }, { 3, 1, 2 } }; // Size of matrix r = M.size(), c = M[0].size(); // Function call findsumofneighbors(M); } |
Java
// Java program for the above approach import java.util.*; import java.lang.*; public class GFG { // Initialize rows and columns private static int r, c; // Store all 8 directions static int [][] dir = { { 1 , 0 }, { - 1 , 0 }, { 0 , 1 }, { 0 , - 1 }, { - 1 , - 1 }, { - 1 , 1 }, { 1 , 1 }, { 1 , - 1 } }; // Function to check if a cell // (i, j) is valid or not public static boolean valid( int i, int j) { if (i >= 0 && j >= 0 && i < r && j < c) return true ; return false ; } // Function to find sum of adjacent cells // for cell (i, j) static int find( int i, int j, int [][] v) { // Initialize sum int s = 0 ; // Visit all 8 directions for ( int k = 0 ; k < 8 ; k++) { int ni = i + dir[k][ 0 ], nj = j + dir[k][ 1 ]; // Check if cell is valid if (valid(ni, nj)) s += v[ni][nj]; } // Return sum return s; } // Function to print sum of adjacent elements static void findsumofneighbors( int [][] M) { // Stores the resultant matrix int [][] v = new int [r]; // Iterate each elements of matrix for ( int i = 0 ; i < r; i++) { for ( int j = 0 ; j < c; j++) { // Find adjacent sum v[i][j] = find(i, j, M); System.out.print(v[i][j] + " " ); } System.out.println( "" ); } } // Driver code public static void main(String[] args) { // Given matrix int [][] M = { { 1 , 4 , 1 }, { 2 , 4 , 5 }, { 3 , 1 , 2 } }; // Size of matrix r = M.length; c = M[ 0 ].length; // Function call findsumofneighbors(M); } } // This code is contributed by ajaykr00kj |
Python3
# Python program for the above approach # Initialize rows and columns r, c = 0 , 0 ; # Store all 8 directions dir = [[ 1 , 0 ], [ - 1 , 0 ], [ 0 , 1 ], [ 0 , - 1 ], [ - 1 , - 1 ], [ - 1 , 1 ], [ 1 , 1 ], [ 1 , - 1 ]]; # Function to check if a cell # (i, j) is valid or not def valid(i, j): if (i > = 0 and j > = 0 and i < r and j < c): return True ; return False ; # Function to find sum of adjacent cells # for cell (i, j) def find(i, j, v): # Initialize sum s = 0 ; # Visit all 8 directions for k in range ( 8 ): ni = i + dir [k][ 0 ]; nj = j + dir [k][ 1 ]; # Check if cell is valid if (valid(ni, nj)): s + = v[ni][nj]; # Return sum return s; # Function to print sum of adjacent elements def findsumofneighbors(M): # Stores the resultant matrix v = [[ 0 for i in range (c)] for j in range (r)]; # Iterate each elements of matrix for i in range (r): for j in range (c): # Find adjacent sum v[i][j] = find(i, j, M); print (v[i][j], end = " " ); print (""); # Driver code if __name__ = = '__main__' : # Given matrix M = [[ 1 , 4 , 1 ], [ 2 , 4 , 5 ], [ 3 , 1 , 2 ]]; # Size of matrix r = len (M[ 0 ]); c = len (M[ 1 ]); # Function call findsumofneighbors(M); # This code is contributed by 29AjayKumar |
C#
// C# program for the above approach using System; public class GFG { // Initialize rows and columns private static int r, c; // Store all 8 directions static int [,] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 } }; // Function to check if a cell // (i, j) is valid or not public static bool valid( int i, int j) { if (i >= 0 && j >= 0 && i < r && j < c) return true ; return false ; } // Function to find sum of adjacent cells // for cell (i, j) static int find( int i, int j, int [,] v) { // Initialize sum int s = 0; // Visit all 8 directions for ( int k = 0; k < 8; k++) { int ni = i + dir[k, 0], nj = j + dir[k, 1]; // Check if cell is valid if (valid(ni, nj)) s += v[ni, nj]; } // Return sum return s; } // Function to print sum of adjacent elements static void findsumofneighbors( int [,] M) { // Stores the resultant matrix int [,] v = new int [r, c]; // Iterate each elements of matrix for ( int i = 0; i < r; i++) { for ( int j = 0; j < c; j++) { // Find adjacent sum v[i,j] = find(i, j, M); Console.Write(v[i, j] + " " ); } Console.WriteLine( "" ); } } // Driver code public static void Main(String[] args) { // Given matrix int [,] M = { { 1, 4, 1 }, { 2, 4, 5 }, { 3, 1, 2 } }; // Size of matrix r = M.GetLength(0); c = M.GetLength(1); // Function call findsumofneighbors(M); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program for the above approach // Initialize rows and columns let r, c; // Store all 8 directions let dir = [[ 1, 0 ], [ -1, 0 ], [ 0, 1 ], [ 0, -1 ], [ -1, -1 ], [ -1, 1 ], [ 1, 1 ], [ 1, -1 ]]; // Function to check if a cell // (i, j) is valid or not function valid(i, j) { if (i >= 0 && j >= 0 && i < r && j < c) return true ; return false ; } // Function to find sum of adjacent cells // for cell (i, j) function find(i, j, v) { // Initialize sum let s = 0; // Visit all 8 directions for (let k = 0; k < 8; k++) { let ni = i + dir[k][0], nj = j + dir[k][1]; // Check if cell is valid if (valid(ni, nj)) s += v[ni][nj]; } // Return sum return s; } // Function to print sum of adjacent elements function findsumofneighbors(M) { // Stores the resultant matrix let v = new Array(r); // Loop to create 2D array using 1D array for ( var i = 0; i < v.length; i++) { v[i] = new Array(2); } // Iterate each elements of matrix for (let i = 0; i < r; i++) { for (let j = 0; j < c; j++) { // Find adjacent sum v[i][j] = find(i, j, M); document.write(v[i][j] + " " ); } document.write( "<br/>" ); } } // Driver Code // Given matrix let M = [[ 1, 4, 1 ], [ 2, 4, 5 ], [ 3, 1, 2 ]]; // Size of matrix r = M.length; c = M[0].length; // Function call findsumofneighbors(M); </script> |
10 13 13 13 19 12 7 16 10
Time Complexity: O(N*M) where N * M are the dimensions of the matrix.
Auxiliary Space: O(N*M)