Given a matrix mat[][] with dimensions M * N, the task is to replace each matrix elements with the maximum sum of its left or right diagonal.
Examples:
Input: mat[][] = {{5, 2, 1}, {7, 2, 6}, {3, 1, 9}}
Output:
16 9 6
9 16 8
6 8 16
Explanation:
Replace each element with max(sum of right diagonal, sum of left diagonal).
Follow the diagram below to understand more clearly.Input: mat[][] = {{1, 2}, {3, 4}}
Output:
5 5
5 5
Approach: The main idea is based on the facts based on the observation stated below:
- Sum of row and column indices for the right diagonal elements are equal.
- Difference between the row and column indices for left diagonal elements is equal.
- Using the above two properties to store the sum of the left and right diagonals of each element using a Map.
- Traverse the matrix and replace each element with the maximum of left diagonal sum or right diagonal sum.
- Print the final matrix obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to update given matrix with // maximum of left and right diagonal sum void updateMatrix( int mat[][3]) { // Stores the total sum // of right diagonal map< int , int > right; // Stores the total sum // of left diagonal map< int , int > left; for ( int i = 0; i < 3; i++) { for ( int j = 0; j < 3; j++) { // Update the map storing // right diagonal sums if (right.find(i + j) == right.end()) right[i + j] = mat[i][j]; else right[i + j] += mat[i][j]; // Update the map storing // left diagonal sums if (left.find(i - j) == left.end()) left[i - j] = mat[i][j]; else left[i - j] += mat[i][j]; } } // Traverse the matrix for ( int i = 0; i < 3; i++) { for ( int j = 0; j < 3; j++) { // Update the matrix mat[i][j] = max(right[i + j], left[i - j]); } } // Print the matrix for ( int i = 0; i < 3; i++) { for ( int j = 0; j < 3; j++) { cout << mat[i][j] << " " ; } cout << endl; } } // Driver code int main() { int mat[][3] = { { 5, 2, 1 }, { 7, 2, 6 }, { 3, 1, 9 } }; updateMatrix(mat); return 0; } // This code is contributed by ukasp. |
Java
// Java program for the above approach // Function to update given matrix with // maximum of left and right diagonal sum import java.io.*; import java.util.*; class GFG { static void updateMatrix( int mat[][]) { Map<Integer, Integer> right = new HashMap<Integer, Integer>(); Map<Integer, Integer> left = new HashMap<Integer, Integer>(); for ( int i = 0 ; i < 3 ; i++) { for ( int j = 0 ; j < 3 ; j++) { // Update the map storing // right diagonal sums if (!right.containsKey(i + j)) right.put(i + j, mat[i][j]); else right.put(i + j, right.get(i + j) + mat[i][j]); // Update the map storing // left diagonal sums if (!left.containsKey(i - j)) left.put(i - j, mat[i][j]); else left.put(i - j, left.get(i - j) + mat[i][j]); } } // Traverse the matrix for ( int i = 0 ; i < 3 ; i++) { for ( int j = 0 ; j < 3 ; j++) { // Update the matrix mat[i][j] = Math.max(right.get(i + j), left.get(i - j)); } } // Print the matrix for ( int i = 0 ; i < 3 ; i++) { for ( int j = 0 ; j < 3 ; j++) { System.out.print(mat[i][j] + " " ); } System.out.print( "\n" ); } } // Driver code public static void main (String[] args) { int [][] mat = {{ 5 , 2 , 1 }, { 7 , 2 , 6 }, { 3 , 1 , 9 }}; updateMatrix(mat); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program for the above approach # Function to update given matrix with # maximum of left and right diagonal sum def updateMatrix(mat): # Stores the total sum # of right diagonal right = {} # Stores the total sum # of left diagonal left = {} for i in range ( len (mat)): for j in range ( len (mat[ 0 ])): # Update the map storing # right diagonal sums if i + j not in right: right[i + j] = mat[i][j] else : right[i + j] + = mat[i][j] # Update the map storing # left diagonal sums if i - j not in left: left[i - j] = mat[i][j] else : left[i - j] + = mat[i][j] # Traverse the matrix for i in range ( len (mat)): for j in range ( len (mat[ 0 ])): # Update the matrix mat[i][j] = max (right[i + j], left[i - j]) # Print the matrix for i in mat: print ( * i) # Given matrix mat = [[ 5 , 2 , 1 ], [ 7 , 2 , 6 ], [ 3 , 1 , 9 ]] updateMatrix(mat) |
C#
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to update given matrix with // maximum of left and right diagonal sum static void updateMatrix( int [,] mat) { // Stores the total sum // of right diagonal Dictionary< int , int > right = new Dictionary< int , int >(); // Stores the total sum // of left diagonal Dictionary< int , int > left = new Dictionary< int , int >(); for ( int i = 0; i < 3; i++) { for ( int j = 0; j < 3; j++) { // Update the map storing // right diagonal sums if (!right.ContainsKey(i + j)) right[i + j] = mat[i,j]; else right[i + j] += mat[i,j]; // Update the map storing // left diagonal sums if (!left.ContainsKey(i - j)) left[i - j] = mat[i,j]; else left[i - j] += mat[i,j]; } } // Traverse the matrix for ( int i = 0; i < 3; i++) { for ( int j = 0; j < 3; j++) { // Update the matrix mat[i,j] = Math.Max(right[i + j], left[i - j]); } } // Print the matrix for ( int i = 0; i < 3; i++) { for ( int j = 0; j < 3; j++) { Console.Write(mat[i,j] + " " ); } Console.WriteLine(); } } static void Main () { int [,] mat = { { 5, 2, 1 }, { 7, 2, 6 }, { 3, 1, 9 } }; updateMatrix(mat); } } // This code is contributed by suresh07. |
Javascript
<script> // Javascript program for the above approach // Function to update given matrix with // maximum of left and right diagonal sum function updateMatrix(mat) { // Stores the total sum // of right diagonal let right = new Map(); // Stores the total sum // of left diagonal let left = new Map(); for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { // Update the map storing // right diagonal sums if (!right.has(i + j)) right.set(i + j, mat[i][j]); else right.set(i + j, right.get(i + j) + mat[i][j]); // Update the map storing // left diagonal sums if (!left.has(i - j)) left.set(i - j, mat[i][j]); else left.set(i - j, left.get(i - j) + mat[i][j]); } } // Traverse the matrix for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { // Update the matrix mat[i][j] = Math.max(right.get(i + j), left.get(i - j)); } } // Print the matrix for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { document.write(mat[i][j] + " " ); } document.write( "<br>" ); } } // Driver code let mat = [ [ 5, 2, 1 ], [ 7, 2, 6 ], [ 3, 1, 9 ] ]; updateMatrix(mat); // This code is contributed by gfgking. </script> |
16 9 6 9 16 8 6 8 16
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!