Problem statement

Given a square matrix mat, return the sum of the primary diagonal and the part of the secondary diagonal not on the primary diagonal (the center of an odd-sized matrix counts once).

Example 1

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: 25
Explanation: 1+5+9 + 3+7 = 25 (5 counted once).

Example 2

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

Constraints

• 1 <= n <= 8
• 1 <= mat[i][j] <= 100

Hints for Matrix Diagonal Sum

1. Hint 1

   Primary: mat[i][i]. Secondary: mat[i][n-1-i].

2. Hint 2

   For odd n, subtract the center once — it was added twice.

How to solve Matrix Diagonal Sum

Both diagonals can be read off with a single index. Walking i down the rows, the primary diagonal is mat[i][i] and the secondary is mat[i][n-1-i]. The only subtlety is that on an odd-sized matrix the two meet at the centre, which must not be counted twice.

Approach

1. Loop i from 0 to n - 1, adding mat[i][i] and mat[i][n - 1 - i].
2. If n is odd, subtract the centre cell mat[n/2][n/2] once.
3. Return the total.

Why it works

The primary diagonal is exactly the cells where row equals column, and the secondary is where the indices sum to n - 1. Those two conditions coincide only when 2i = n - 1, which has an integer solution precisely when n is odd — a single cell, the centre. So the double-count is always either zero cells or exactly one, and subtracting it once fixes the total.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Forgetting the odd-size correction double-counts the centre; this is the entire difficulty of the problem.
• The secondary diagonal index is n - 1 - i, not n - i.
• One loop suffices — there is no need to scan the whole matrix, which would be O(n^2).
• For even n the diagonals never intersect, so no correction applies.

Reference solution

Python

from typing import List

def diagonalSum(mat: List[List[int]]) -> int:
    n = len(mat)
    total = 0
    for i in range(n):
        total += mat[i][i] + mat[i][n - 1 - i]
    if n % 2 == 1:
        total -= mat[n // 2][n // 2]
    return total

Java

public static int diagonalSum(int[][] mat) {
    int n = mat.length, total = 0;
    for (int i = 0; i < n; i++) total += mat[i][i] + mat[i][n - 1 - i];
    if (n % 2 == 1) total -= mat[n / 2][n / 2];
    return total;
}

C++

int diagonalSum(vector<vector<int>>& mat) {
    int n = (int) mat.size(), total = 0;
    for (int i = 0; i < n; i++) total += mat[i][i] + mat[i][n - 1 - i];
    if (n % 2 == 1) total -= mat[n / 2][n / 2];
    return total;
}

JavaScript

var diagonalSum = function(mat) {
    const n = mat.length;
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += mat[i][i] + mat[i][n - 1 - i];
    }
    if (n % 2 === 1) sum -= mat[(n - 1) / 2][(n - 1) / 2];
    return sum;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy