Code Implementation

class Solution:
    def diagonalSum(self, mat):
        n = len(mat)
        total = 0
        for i in range(n):
            total += mat[i][i]  # Primary diagonal
            total += mat[i][n - 1 - i]  # Secondary diagonal
        if n % 2 == 1:
            total -= mat[n // 2][n // 2]  # Subtract the center if counted twice
        return total
      

class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int n = mat.size();
        int total = 0;
        for (int i = 0; i < n; ++i) {
            total += mat[i][i]; // Primary diagonal
            total += mat[i][n - 1 - i]; // Secondary diagonal
        }
        if (n % 2 == 1) {
            total -= mat[n / 2][n / 2]; // Subtract center if counted twice
        }
        return total;
    }
};
      

class Solution {
    public int diagonalSum(int[][] mat) {
        int n = mat.length;
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += mat[i][i]; // Primary diagonal
            total += mat[i][n - 1 - i]; // Secondary diagonal
        }
        if (n % 2 == 1) {
            total -= mat[n / 2][n / 2]; // Subtract center if counted twice
        }
        return total;
    }
}
      

/**
 * @param {number[][]} mat
 * @return {number}
 */
var diagonalSum = function(mat) {
    const n = mat.length;
    let total = 0;
    for (let i = 0; i < n; i++) {
        total += mat[i][i]; // Primary diagonal
        total += mat[i][n - 1 - i]; // Secondary diagonal
    }
    if (n % 2 === 1) {
        total -= mat[Math.floor(n / 2)][Math.floor(n / 2)]; // Subtract center if counted twice
    }
    return total;
};
      

Problem Description

You are given a square matrix mat of size n x n, where each element is an integer. Your task is to return the sum of the matrix's primary and secondary diagonals.

• The primary diagonal runs from the top-left to the bottom-right of the matrix (elements mat[i][i]).
• The secondary diagonal runs from the top-right to the bottom-left (elements mat[i][n-1-i]).
• If the size of the matrix n is odd, the center element belongs to both diagonals, so it should only be counted once in the sum.

Constraints:

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

Thought Process

Let's break down the problem. We need to sum all the numbers that are on either of the two diagonals of the matrix. At first glance, a brute-force method would be to loop through every element and check if it belongs to either diagonal, but that's inefficient.

Instead, we notice that for a square matrix, the diagonal elements have predictable positions:

• Primary diagonal: mat[i][i] for all i
• Secondary diagonal: mat[i][n-1-i] for all i

However, if n is odd, the center element (where i == n/2) gets counted twice (once for each diagonal). We need to subtract it once to avoid double-counting.

Solution Approach

Let's outline the efficient solution step by step:

1. Initialize a total sum variable. We'll accumulate the sum of both diagonals here.
2. Loop through the matrix from 0 to n-1:
   • Add mat[i][i] (primary diagonal) to the total.
   • Add mat[i][n-1-i] (secondary diagonal) to the total.
3. Adjust for double-counted center (if n is odd):
   • When n is odd, the center element at mat[n//2][n//2] appears in both diagonals. Subtract it once from the total.
4. Return the total sum.

This approach is efficient because we only loop through the matrix once, and we avoid unnecessary checks or extra data structures.

Example Walkthrough

Let's consider the example matrix:

mat = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
  

• Primary diagonal: 1 (mat[0][0]), 5 (mat[1][1]), 9 (mat[2][2])
• Secondary diagonal: 3 (mat[0][2]), 5 (mat[1][1]), 7 (mat[2][0])

Step by step:

1. Initialize total = 0
2. i = 0: total += 1 (primary), total += 3 (secondary) → total = 4
3. i = 1: total += 5 (primary), total += 5 (secondary) → total = 14
4. i = 2: total += 9 (primary), total += 7 (secondary) → total = 30
5. The center (mat[1][1] = 5) was counted twice (once for each diagonal), so subtract it once: total = 30 - 5 = 25

Final answer: 25

Time and Space Complexity

• Brute-force approach:
  • Loop through every element and check if it lies on a diagonal: O(n^2) time.
  • No extra space needed: O(1) space.
• Optimized approach (our solution):
  • Only one loop through n rows: O(n) time.
  • No extra data structures: O(1) space.

The optimized solution is much faster and uses minimal memory, making it suitable even for the largest allowed matrices.

Summary

To solve the Matrix Diagonal Sum problem, we efficiently sum both diagonals by leveraging their predictable positions in the matrix. We loop through each row once, adding both diagonal elements, and adjust for a possible double-counted center if the matrix size is odd. This results in a clean, O(n) time and O(1) space solution that is both elegant and easy to implement.