Matrix Diagonal Sum

How it works

We can directly compute both diagonal sums in a single pass. For row r, the primary diagonal element is at column r, and the secondary diagonal element is at column n - r - 1. We simply add both for each row. When n is odd, the center element (at row n / 2, column n / 2) is counted twice, so we subtract it once at the end.

Steps

1. Initialize the result sum to 0.
2. For each row index r from 0 to n - 1:
   • Add mat[r][r] (primary diagonal element).
   • Add mat[r][n - r - 1] (secondary diagonal element).
3. If n is odd, subtract the center element mat[n / 2][n / 2] to correct for double-counting.
4. Return the result.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Double-Counting the Center Element for Odd-Sized Matrices

When the matrix has an odd dimension, the center element lies on both diagonals and gets added twice. You must subtract it once at the end. Forgetting this check causes incorrect results for odd-sized matrices like 3x3 or 5x5.

Using Incorrect Index Formula for Secondary Diagonal

The secondary diagonal element in row r is at column n - r - 1, not n - r. Using the wrong formula causes an index out of bounds error or accesses the wrong elements.

from typing import List

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        res, n = 0, len(mat)

        for r in range(n):
            res += mat[r][r]
            res += mat[r][n - r - 1]

        return res - (mat[n // 2][n // 2] if n & 1 else 0)

class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int res = 0, n = mat.size();

        for (int r = 0; r < n; r++) {
            res += mat[r][r];
            res += mat[r][n - r - 1];
        }

        return res - (n % 2 == 1 ? mat[n / 2][n / 2] : 0);
    }
};