Matrix Diagonal Sum — Solution

Problem

Given a square matrix of integers, return the sum of all elements that lie on the primary diagonal (top-left to bottom-right) or the secondary diagonal (top-right to bottom-left). If the matrix has an odd number of rows, the center element sits on both diagonals — count it only once.

• Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
• Output: 25
• Explanation: Primary diagonal gives 1, 5, 9; secondary gives 3, 5, 7; center 5 appears in both, so 1+3+5+9+7 = 25.

Counter-example showing the overlap: for a 3×3 matrix the center is at mat[1][1]. Both diagonals pass through it, so a naive double-count yields 30 — subtracting 5 once gives the correct 25.

Intuition

Each row contributes exactly one element to the primary diagonal and one to the secondary. Walking rows once is all that's needed. The only wrinkle is that when n is odd the center element lands in both sets — a single conditional subtraction after the loop handles it cleanly.

Solution — Single Pass

Walk through every row, adding both diagonal elements, then correct for the double-counted center if n is odd.

1. Get the matrix size n.
2. Initialize total = 0.
3. For each row index i, add mat[i][i] (primary) and mat[i][n-1-i] (secondary) to total.
4. If n is odd, subtract mat[n//2][n//2] — the center was added in step 3 as both diagonals' contribution.
5. Return total.

1def diagonalSum(mat: list[list[int]]) -> int:
2    n = len(mat)
3    total = 0
4    for i in range(n):
5        total += mat[i][i]            # primary diagonal element for this row
6        total += mat[i][n - 1 - i]   # secondary diagonal element for this row
7    if n % 2 == 1:
8        total -= mat[n // 2][n // 2]  # center was included in both diagonals above
9    return total

Time: O(n) — one pass through n rows, each doing constant work.
Space: O(1) — only a running total is kept.

Complexity Summary

Common Mistakes

• Forgetting the center subtraction for odd n — when n is odd, mat[n//2][n//2] satisfies both row == col and row + col == n-1, so the loop adds it twice; skip the check and the answer is off by that value.
• Using n - i instead of n - 1 - i for the secondary diagonal column — the secondary element in row i is at column n - 1 - i (zero-indexed), not n - i, which would be out of bounds on the last row.
• Reaching for a nested O(n²) loop — iterating every cell and checking if row == col or row + col == n - 1 works but is unnecessary; the single-row loop is both simpler and faster.
• Checking n % 2 == 0 to decide whether to subtract the center — only odd-sized matrices have a center that straddles both diagonals, so the condition should be n % 2 == 1.

Related Problems

• spiral-matrix — traversing a 2D matrix by manipulating row and column indices explicitly
• rotate-image — in-place matrix transformation that relies on the same diagonal index arithmetic
• set-matrix-zeroes — modifying matrix elements based on which row/column they occupy
• reshape-the-matrix — mapping 2D matrix positions to a flat index and back
• search-a-2d-matrix — treating matrix coordinates as first-class values for efficient access