#1572
Matrix Diagonal Sum
Easy Index patterns
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Sum the primary and secondary diagonals of a square matrix, counting the centre only once when n is odd.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: add both diagonals, counting the centre once.
Why this works: one loop reads mat[i][i] and mat[i][n-1-i]; for odd n they meet in the middle.
Example: [[1,2,3],[4,5,6],[7,8,9]]
primary 1+5+9 = 15, secondary 3+5+7 = 1530 - 5 (centre twice) = 25
✦Hints open one at a time
Primary diagonal: mat[i][i]. Secondary: mat[i][n - 1 - i].
They overlap only when i == n - 1 - i.
↗Approach
One loop over i adding both diagonal cells, then subtract the centre once if n is odd.
</>Solution (Java)
class Solution {
public int diagonalSum(int[][] mat) {
int n = mat.length, sum = 0;
for (int i = 0; i < n; i++) {
sum += mat[i][i] + mat[i][n - 1 - i];
}
if (n % 2 == 1) sum -= mat[n / 2][n / 2]; // centre counted twice
return sum;
}
}!Common mistake
Looping over all n² cells checking conditions — works, but O(n²).
Complexity
- Time: O(n).
- Space: O(1).
Topic: 2D Arrays & Matrix
🎬 Episode 14: video coming soon