{x}
blog image

Matrix Diagonal Sum

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

 

Example 1:

Input: mat = [[1,2,3],
              [4,5,6],
              [7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.

Example 2:

Input: mat = [[1,1,1,1],
              [1,1,1,1],
              [1,1,1,1],
              [1,1,1,1]]
Output: 8

Example 3:

Input: mat = [[5]]
Output: 5

 

Constraints:

  • n == mat.length == mat[i].length
  • 1 <= n <= 100
  • 1 <= mat[i][j] <= 100

Solution Explanation for 1572. Matrix Diagonal Sum

This problem asks us to find the sum of elements in the primary and secondary diagonals of a square matrix, excluding the element at the intersection of the two diagonals (if the matrix has an odd number of rows and columns).

Approach:

The most efficient way to solve this is through direct iteration. We iterate through the rows of the matrix. For each row, we add the element at the index i (primary diagonal) and the element at index n-1-i (secondary diagonal) to the sum. We need a check to avoid double-counting the central element (when the matrix dimension is odd).

Code Implementation (Python):

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        n = len(mat)
        total_sum = 0
        for i in range(n):
            total_sum += mat[i][i]  # Primary diagonal
            if i != n - 1 - i:  # Avoid double counting for odd-sized matrices
                total_sum += mat[i][n - 1 - i] #Secondary Diagonal
        return total_sum

Time and Space Complexity Analysis:

  • Time Complexity: O(n), where n is the number of rows (and columns) in the square matrix. We iterate through the rows once.

  • Space Complexity: O(1). We only use a constant amount of extra space to store the total_sum.

Code Implementation in other Languages:

The logic remains consistent across different languages. Here are examples in Java, C++, and Javascript:

Java:

class Solution {
    public int diagonalSum(int[][] mat) {
        int n = mat.length;
        int totalSum = 0;
        for (int i = 0; i < n; i++) {
            totalSum += mat[i][i];
            if (i != n - 1 - i) {
                totalSum += mat[i][n - 1 - i];
            }
        }
        return totalSum;
    }
}

C++:

class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int n = mat.size();
        int totalSum = 0;
        for (int i = 0; i < n; i++) {
            totalSum += mat[i][i];
            if (i != n - 1 - i) {
                totalSum += mat[i][n - 1 - i];
            }
        }
        return totalSum;
    }
};

Javascript:

/**
 * @param {number[][]} mat
 * @return {number}
 */
var diagonalSum = function(mat) {
    let n = mat.length;
    let totalSum = 0;
    for (let i = 0; i < n; i++) {
        totalSum += mat[i][i];
        if (i != n - 1 - i) {
            totalSum += mat[i][n - 1 - i];
        }
    }
    return totalSum;
};

All these solutions have the same time and space complexity as the Python solution. The core algorithm remains unchanged.