Matrix manipulation is a common theme in computer science, with applications ranging from computer graphics to machine learning. The problem of “Matrix Diagonal Sum” featured on Leetcode tests your ability to navigate and manipulate 2D arrays effectively. This article provides an in-depth analysis of the problem, multiple ways to solve it, and a thorough comparison of these methods.

## Problem Statement

Given a square matrix `mat`

, return the sum of the matrix diagonals. Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are distinct from those on the primary diagonal.

### Constraints:

`n == mat.length == mat[i].length`

`1 <= n <= 100`

`1 <= mat[i][j] <= 100`

### Example

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

, the answer would be `1 + 5 + 9 + 3 + 7 = 25`

.

## Naive Approach: Iterative Summation

### Algorithm:

- Initialize a variable
`result`

to 0. - Iterate through each element on the primary diagonal, adding them to
`result`

. - Iterate through each element on the secondary diagonal, adding them to
`result`

. - Return
`result`

.

#### Python Implementation:

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

### Time Complexity:

The time complexity is O(n).

### Space Complexity:

The space complexity is O(1).

## Optimized Approach: Single-Pass Summation

### Algorithm:

- Initialize
`result`

to 0. - Iterate through the matrix in a single pass, adding the diagonal elements to
`result`

. - If the matrix has an odd length, subtract the middle element once to correct for overcounting.

#### Python Implementation:

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

### Time Complexity:

The time complexity is O(n).

### Space Complexity:

The space complexity is O(1).

## Comparison of Approaches

## Conclusion

The “Matrix Diagonal Sum” problem is an excellent example of how a seemingly simple problem can have multiple solutions, each with its own trade-offs. The naive approach is straightforward but uses two loops, whereas the optimized approach accomplishes the task in a single pass.