Data Modelling & AI Data Structure & Algorithm

Find the maximum sum of diagonals for each cell of the Matrix

29 July 2024

0

Given a matrix arr[][] of size N * M, the task is to find the maximum sum of diagonals for each cell of the matrix including that particular element also.

Examples:

Input: N = 4, M = 4
1 2 2 1
2 4 2 4
2 2 3 1
2 4 2 4
Output: 20
Explanation: For this example the maximum sum can be achieved by considering sum over all diagonal element for matrix cell arr[2][2] {0 base indexing}. The diagonal elements of arr[2][2] (=3) is { 1, 4, 3, 4, 4, 4}. Sum overall diagonal elements( and along with the desire element) about desire element arr[2][2](=3) is {1+4+3+4+4+4 = 20} which is the maximum diagonal sum .

Input: N = 3, M = 3
0 1 1
1 0 1
1 1 0
Output: 3
Explanation: If we consider the sum of all diagonal element with respect to arr[2][[1] element then we get the maximum sum. The diagonal sum with respect to arr[2][1] is { 1 + 1+ 1 = 3} which is the maximum diagonal sum in this example.

Approach: This can be solved with the following idea:

The problem can be solved using Nested Loop . The idea here is that each matrix element has 4 diagonal direction –

North-East,

North-West,

South-East,

South-West

For each matrix element, arr[i][j] we will calculate the sum of all element present in it’s North-East, North-West, South-East, South-West direction, Keep one thing in mind that we will do operations within the matrix bound .

Follow the steps below to solve the problem:

Initialize two variables, say, N and M, to store the row and column number of the matrix.
Initialize a 2D array of integers, arr[N][M].
Initialize two variables, say, ci and cj, to store the current index of element, arr[i][j] whose overall diagonal sum is going to be calculated.
Initialize the variable, say, ans, to store the maximum sum over all diagonals for each matrix element.
Now, traverse the whole matrix/2D array, arr[N][M].
Inside Nested Loop, initialize one variable, say, present_sum, which is used to store the present diagonal sum for each element.
Inside Nested Loop, assign ci to row number(i) and cj to column number(j).
Whenever we calculate the sum in any diagonal direction about arr[i][j] inside the matrix each time we will use a Loop to move in this direction.
Calculate the present diagonal sum of arr[i][j] in its North-West direction.
To process the element present in the North-West direction we will always decrease ci and cj by 1 and before decreasing we add that element in the previous_sum variable.
Again restore the current index of the element arr[i][j] in the ci and cj variable to calculate the sum in the other 3 diagonal directions (North-East, South-West, South-East).
Calculate the present diagonal sum of arr[i][j] in its North-East direction.
To process the element present in the North-East direction we will always decrease ci and increase cj by 1 and before it, we add those elements in the previous_sum variable.
Again restore the current index of the element arr[i][j] in the ci and cj variable to calculate the sum in the other 2 diagonal directions (South-West, South-East).
Calculate the present diagonal sum of arr[i][j] in its South-West direction.
To process the element present in the South-West direction we will always increase ci and decrease cj by 1 and before it, we add those elements in the previous_sum variable.
Again restore the current index of the element arr[i][j] in the ci and cj variable to calculate the sum in the other 1 diagonal direction(South-East).
Calculate the present diagonal sum of arr[i][j] in its South-East direction.
To process the element present in the South-East direction we will always increase ci and increase cj by 1 and before it, we add those elements in the previous_sum variable.
Restore the current index in ci and cj.
In every four directions (North-West, North-East, South-West, South-East) we have added the element, arr[i][j] 4 times in the present_sum variable, so we have to subtract this element from present_sum by 3 times.
Now store the maximum sum over all diagonal of the matrix element in ans variable by doing ans = max(ans, present_sum).
Print the answer.

Below is the implementation of the code:

C++

// C++ Implementation
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate maximum
// diagonal sum
void maxDiagonalSum(int N, int M, vector<vector<int> >& a)
{
    int ci, cj;
 
    // Initialize the ans variable to
    // store the maximum sum over all
    // diagonal of matrix element
    int ans = INT_MIN;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
 
            // Present_sum, which is used
            // to store the present diagonal
            // sum for each element
            int present_sum = 0;
 
            // ci and cj, to store the
            // current index of element,
            // arr[i][j]
            ci = i, cj = j;
 
            // Calculate present diagonal
            // sum of arr[i][j] in it's
            // North-West direction
            while (ci >= 0 && ci < N && cj >= 0 && cj < M) {
 
                // Add each element present
                // in North-West diresction
                // with respectto arr[i][j]
                // in present_sum variable
                present_sum += a[ci][cj];
 
                // Move on North-West
                // direction by reducing
                // ci and cj
                ci--;
                cj--;
            }
 
            // Again restore the current
            // index of the element
            // arr[i][j] to calculate
            // sum in other 3 diagonal
            // direction
            ci = i, cj = j;
 
            // Calculate present diagonal
            // sum of arr[i][j] in it's
            // North-East direction
            while (ci >= 0 && ci < N && cj >= 0 && cj < M) {
 
                // Add each element present
                // in North-East diresction
                // with respect to arr[i][j]
                // in present_sum
                present_sum += a[ci][cj];
 
                // Move on North-East direction
                // By reducing ci and
                // By increasing cj
                ci--;
                cj++;
            }
 
            // Again restore the current
            // index of the element
            // arr[i][j] to calculate sum
            // in other 2 diagonal
            // direction
            ci = i, cj = j;
 
            // Calculate present diagonal
            // sum of arr[i][j] in it's
            // South-West direction
            while (ci >= 0 && ci < N && cj >= 0 && cj < M) {
 
                // Add each element present
                // in South-West diresction
                // with respect to arr[i][j]
                // in present_sum variable
                present_sum += a[ci][cj];
 
                // Move on South-West direction
                // By increasing ci and
                // By decreasing cj
                ci++;
                cj--;
            }
 
            // Again restore the current
            // index of the element
            // arr[i][j] to calculate sum
            // in other 1 diagonal direction
            ci = i, cj = j;
 
            // Calculate present diagonal
            // sum of arr[i][j] in it's
            // South-East direction
            while (ci >= 0 && ci < N && cj >= 0 && cj < M) {
 
                // Add each element present
                // in South-East direction
                // with respect to arr[i][j]
                // ]in present_sum variable
                present_sum += a[ci][cj];
 
                // Move on South-West direction
                // By increasing ci and
                // By increasing cj
                ci++;
                cj++;
            }
 
            // Restore the current index
            ci = i, cj = j;
 
            // As we have added the element,
            // arr[i][j] 4 times in
            // present_sum variable because
            // in each 4 direction we have
            // added this element in
            // present_sum variable, so
            // we have to subtract this
            // element from present_sum
            // variable By 3 times
            present_sum -= 3 * a[ci][cj];
 
            // Now store the maximum sum
            // over all diagonal of matrix
            // element in ans variable
            ans = max(ans, present_sum);
        }
    }
 
    // Now print the answer
    cout << ans << "\n";
}
 
// Driver Code
int main()
{
    int N, M;
    N = 4, M = 4;
 
    // Initialize the 2D array
    vector<vector<int> > arr = { { 1, 2, 2, 1 },
                                 { 2, 4, 2, 4 },
                                 { 2, 2, 3, 1 },
                                 { 2, 4, 2, 4 } };
 
    // Function call
    maxDiagonalSum(N, M, arr);
 
    return 0;
}

Java

// Java Implementation
 
import java.util.*;
 
public class GFG {
    // Function to calculate maximum
    // diagonal sum
    public static void
    maxDiagonalSum(int N, int M, List<List<Integer> > a)
    {
        int ci, cj;
       
        // Initialize the ans variable to
        // store the maximum sum over all
        // diagonal of matrix element
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
               
                // Present_sum, which is used
                // to store the present diagonal
                // sum for each element
                int present_sum = 0;
 
                // ci and cj, to store the
                // current index of element,
                // arr[i][j]
                ci = i;
                cj = j;
 
                // Calculate present diagonal
                // sum of arr[i][j] in it's
                // North-West direction
                while (ci >= 0 && ci < N && cj >= 0
                       && cj < M) {
                   
                    // Add each element present
                    // in North-West diresction
                    // with respectto arr[i][j]
                    // in present_sum variable
                    present_sum += a.get(ci).get(cj);
 
                    // Move on North-West
                    // direction by reducing
                    // ci and cj
                    ci--;
                    cj--;
                }
 
                // Again restore the current
                // index of the element
                // arr[i][j] to calculate
                // sum in other 3 diagonal
                // direction
                ci = i;
                cj = j;
 
                // Calculate present diagonal
                // sum of arr[i][j] in it's
                // North-East direction
                while (ci >= 0 && ci < N && cj >= 0
                       && cj < M) {
 
                    // Add each element present
                    // in North-East diresction
                    // with respect to arr[i][j]
                    // in present_sum
                    present_sum += a.get(ci).get(cj);
 
                    // Move on North-East direction
                    // By reducing ci and
                    // By increasing cj
                    ci--;
                    cj++;
                }
 
                // Again restore the current
                // index of the element
                // arr[i][j] to calculate sum
                // in other 2 diagonal
                // direction
                ci = i;
                cj = j;
 
                // Calculate present diagonal
                // sum of arr[i][j] in it's
                // South-West direction
                while (ci >= 0 && ci < N && cj >= 0
                       && cj < M) {
 
                    // Add each element present
                    // in South-West diresction
                    // with respect to arr[i][j]
                    // in present_sum variable
                    present_sum += a.get(ci).get(cj);
 
                    // Move on South-West direction
                    // By increasing ci and
                    // By decreasing cj
                    ci++;
                    cj--;
                }
 
                // Again restore the current
                // index of the element
                // arr[i][j] to calculate sum
                // in other 1 diagonal direction
                ci = i;
                cj = j;
 
                // Calculate present diagonal
                // sum of arr[i][j] in it's
                // South-East direction
                while (ci >= 0 && ci < N && cj >= 0
                       && cj < M) {
                   
                    // Add each element present
                    // in South-East direction
                    // with respect to arr[i][j]
                    // ]in present_sum variable
                    present_sum += a.get(ci).get(cj);
 
                    // Move on South-West direction
                    // By increasing ci and
                    // By increasing cj
                    ci++;
                    cj++;
                }
 
                // Restore the current index
                ci = i;
                cj = j;
 
                // As we have added the element,
                // arr[i][j] 4 times in
                // present_sum variable because
                // in each 4 direction we have
                // added this element in
                // present_sum variable, so
                // we have to subtract this
                // element from present_sum
                // variable By 3 times
                present_sum -= 3 * a.get(ci).get(cj);
 
                // Now store the maximum sum
                // over all diagonal of matrix
                // element in ans variable
                ans = Math.max(ans, present_sum);
            }
        }
 
        // Now print the answer
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 4, M = 4;
        // Initialize the 2D array
        List<List<Integer> > arr = new ArrayList<>();
        arr.add(Arrays.asList(1, 2, 2, 1));
        arr.add(Arrays.asList(2, 4, 2, 4));
        arr.add(Arrays.asList(2, 2, 3, 1));
        arr.add(Arrays.asList(2, 4, 2, 4));
 
        // Initialize the 2D array
        maxDiagonalSum(N, M, arr);
    }
}

Python3

# Python Implementation
 
# Function to calculate maximum
# diagonal sum
def max_diagonal_sum(N, M, a):
    # Initialize the ans variable to 
    # store the maximum sum over all 
    # diagonal of matrix element
    ans = float('-inf')
 
    for i in range(N):
        for j in range(M):
            # Present_sum, which is used 
            # to store the present diagonal 
            # sum for each element
            present_sum = 0
 
            # ci and cj, to store the 
            # current index of element, 
            # a[i][j]
            ci = i
            cj = j
 
            # Calculate present diagonal 
            # sum of a[i][j] in its 
            # North-West direction
            while ci >= 0 and ci < N and cj >= 0 and cj < M:
                # Add each element present 
                # in North-West direction 
                # with respect to a[i][j] 
                # to present_sum variable
                present_sum += a[ci][cj]
 
                # Move on North-West 
                # direction by reducing 
                # ci and cj
                ci -= 1
                cj -= 1
 
            # Again restore the current 
            # index of the element 
            # a[i][j] to calculate 
            # sum in other 3 diagonal 
            # directions
            ci = i
            cj = j
 
            # Calculate present diagonal 
            # sum of a[i][j] in its 
            # North-East direction
            while ci >= 0 and ci < N and cj >= 0 and cj < M:
                # Add each element present 
                # in North-East direction 
                # with respect to a[i][j]
                # in present_sum
                present_sum += a[ci][cj]
 
                # Move on North-East direction 
                # By reducing ci and 
                # By increasing cj
                ci -= 1
                cj += 1
 
            # Again restore the current 
            # index of the element 
            # a[i][j] to calculate sum 
            # in other 2 diagonal 
            # directions
            ci = i
            cj = j
 
            # Calculate present diagonal 
            # sum of a[i][j] in its 
            # South-West direction
            while ci >= 0 and ci < N and cj >= 0 and cj < M:
                # Add each element present 
                # in South-West direction 
                # with respect to a[i][j] 
                # in present_sum variable
                present_sum += a[ci][cj]
 
                # Move on South-West direction 
                # By increasing ci and 
                # By decreasing cj
                ci += 1
                cj -= 1
 
            # Again restore the current 
            # index of the element 
            # a[i][j] to calculate sum 
            # in other 1 diagonal direction
            ci = i
            cj = j
 
            # Calculate present diagonal 
            # sum of a[i][j] in its 
            # South-East direction
            while ci >= 0 and ci < N and cj >= 0 and cj < M:
                # Add each element present 
                # in South-East direction 
                # with respect to a[i][j] 
                # to present_sum variable
                present_sum += a[ci][cj]
 
                # Move on South-East direction 
                # By increasing ci and 
                # By increasing cj
                ci += 1
                cj += 1
 
            # Restore the current index
            ci = i
            cj = j
 
            # As we have added the element,
            # a[i][j] 4 times in 
            # present_sum variable because
            # in each 4 direction we have 
            # added this element in 
            # present_sum variable, so
            # we have to subtract this 
            # element from present_sum 
            # variable by 3 times
            present_sum -= 3 * a[ci][cj]
 
            # Now store the maximum sum 
            # over all diagonal of matrix 
            # element in ans variable
            ans = max(ans, present_sum)
 
    # Now print the answer
    print(ans)
 
# Driver Code
if __name__ == "__main__":
    N = 4
    M = 4
 
    # Initialize the 2D array
    arr= [
        [1, 2, 2, 1],
        [2, 4, 2, 4],
        [2, 2, 3, 1],
        [2, 4, 2, 4]
    ]
 
    # Function call
    max_diagonal_sum(N, M, arr)
     
 
# This code is contributed by Pushpesh Raj

C#

using System;
using System.Collections.Generic;
 
class GFG {
  static void maxDiagonalSum(int N, int M, List<List<int>> a)
  {
     
    // Initialize the ans variable to
    // store the maximum sum over all
    // diagonal of matrix element
    int ans = int.MinValue;
 
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        // Present_sum, which is used
        // to store the present diagonal
        // sum for each element
        int present_sum = 0;
 
        // Calculate present diagonal
        // sum of arr[i][j] in its
        // North-West direction
        for (int k = 0; k <= Math.Min(i, j); k++) {
          present_sum += a[i - k][j - k];
        }
 
        // Calculate present diagonal
        // sum of arr[i][j] in its
        // South-East direction
        for (int k = 1; i + k < N && j + k < M; k++) {
          present_sum += a[i + k][j + k];
        }
 
        // Calculate present diagonal
        // sum of arr[i][j] in its
        // North-East direction
        for (int k = 1; i - k >= 0 && j + k < M; k++) {
          present_sum += a[i - k][j + k];
        }
 
        // Calculate present diagonal
        // sum of arr[i][j] in its
        // South-West direction
        for (int k = 1; i + k < N && j - k >= 0; k++) {
          present_sum += a[i + k][j - k];
        }
 
        // Now store the maximum sum
        // over all diagonal of matrix
        // element in ans variable
        ans = Math.Max(ans, present_sum);
      }
    }
 
    // Now print the answer
    Console.WriteLine(ans);
  }
 
  // Driver Code
  static void Main(string[] args) {
    int N, M;
    N = 4;
    M = 4;
 
    // Initialize the 2D array
    List<List<int> > arr = new List<List<int> >{
      new List<int>{ 1, 2, 2, 1 },
      new List<int>{ 2, 4, 2, 4 },
      new List<int>{ 2, 2, 3, 1 },
      new List<int>{ 2, 4, 2, 4 }
    };
 
    // Function call
    maxDiagonalSum(N, M, arr);
 
    return;
  }
}
 
//This code is contributed by Akash Jha

Javascript

function maxDiagonalSum(N, M, a) {
  // Initialize the ans 
  //variable to store the maximum sum 
  //over all diagonal of matrix element
  let ans = Number.MIN_SAFE_INTEGER;
 
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      // Present_sum, which is used to store the present diagonal sum for each element
      let present_sum = 0;
 
      // Calculate present diagonal sum of a[i][j] in its North-West direction
      for (let k = 0; k <= Math.min(i, j); k++) {
        present_sum += a[i - k][j - k];
      }
 
      // Calculate present diagonal sum of a[i][j] in its South-East direction
      for (let k = 1; i + k < N && j + k < M; k++) {
        present_sum += a[i + k][j + k];
      }
 
      // Calculate present diagonal sum of a[i][j] in its North-East direction
      for (let k = 1; i - k >= 0 && j + k < M; k++) {
        present_sum += a[i - k][j + k];
      }
 
      // Calculate present diagonal sum of a[i][j] in its South-West direction
      for (let k = 1; i + k < N && j - k >= 0; k++) {
        present_sum += a[i + k][j - k];
      }
 
      // Now store the maximum sum over all diagonal of matrix element in ans variable
      ans = Math.max(ans, present_sum);
    }
  }
 
  // Now return the answer
  return ans;
}
 
// Driver Code
  const N = 4;
  const M = 4;
 
  // Initialize the 2D array
  const arr = [
    [1, 2, 2, 1],
    [2, 4, 2, 4],
    [2, 2, 3, 1],
    [2, 4, 2, 4],
  ];
 
  // Function call
  const result = maxDiagonalSum(N, M, arr);
 
  console.log(result);

Output

Time Complexity: O(N*M*max(N, M))
Auxiliary Space: O(1)

Last Updated :
10 Aug, 2023

Previous

<!–

8 Min Read | Java

–>

Count Subsequences with ordered integers in Array

Next

<!–

8 Min Read | Java

–>

Generic Tree meaning & definition in DSA

Share your thoughts in the comments

Find the maximum sum of diagonals for each cell of the Matrix

C++

Java

Python3

C#

Javascript

Run Local AWS Cloud Stack using LocalStack on Linux

Learn Terraform Automation in 3 days using Video Courses

How To Expose Ansible AWX Service using Nginx Ingress

LEAVE A REPLY Cancel reply

Most Popular

10 Best Antiviruses With a Password Manager in 2025 by Ana Jovanovic

5 Best Internet Security Packages for Laptops in 2025 by Eric Goldstein

5 Best (REALLY FREE) Android Antivirus Apps for 2025 by Hazel Shaw

5 Best Security Apps for Tablets in 2025: Expert Ranked by Sam Boyd

Recent Comments

EDITOR PICKS

10 Best Antiviruses With a Password Manager in 2025 by Ana Jovanovic

5 Best Internet Security Packages for Laptops in 2025 by Eric Goldstein

5 Best (REALLY FREE) Android Antivirus Apps for 2025 by Hazel Shaw

POPULAR POSTS

10 Best Antiviruses With a Password Manager in 2025 by Ana Jovanovic

5 Best Internet Security Packages for Laptops in 2025 by Eric Goldstein

5 Best (REALLY FREE) Android Antivirus Apps for 2025 by Hazel Shaw

POPULAR CATEGORY

ABOUT US

FOLLOW US

Find the maximum sum of diagonals for each cell of the Matrix

C++

Java

Python3

C#

Javascript

Please Login to comment…

LEAVE A REPLY Cancel reply

Most Popular

Recent Comments

EDITOR PICKS

POPULAR POSTS

POPULAR CATEGORY

ABOUT US

FOLLOW US