# Matrix Diagonal Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/matrix-diagonal-sum)
Canonical: https://scaleengineer.com/dsa/problems/matrix-diagonal-sum
**Data structures:** Array, Matrix
---
## Problem
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 not part of the primary diagonal.

**Example 1:**

![](https://assets.glich.co/dsa/matrix-diagonal-sum/image0.png) 

**Input:** mat = [[**1**,2,**3**],
              [4,**5**,6],
              [**7**,8,**9**]]
**Output:** 25
**Explanation:** Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.

**Example 2:**

**Input:** mat = [[**1**,1,1,**1**],
              [1,**1**,**1**,1],
              [1,**1**,**1**,1],
              [**1**,1,1,**1**]]
**Output:** 8

**Example 3:**

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

**Constraints:**

* `n == mat.length == mat[i].length`
* `1 <= n <= 100`
* `1 <= mat[i][j] <= 100`

# Approaches
## Brute Force Iteration
This approach involves iterating through every element of the `n x n` matrix. For each element, we check if it lies on the primary or secondary diagonal. If it does, we add its value to a running total.
**Time:** O(n^2), where `n` is the number of rows (or columns) in the matrix. We visit every element in the matrix. · **Space:** O(1), as we only use a constant amount of extra space for the `sum` variable and loop counters.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large matrices as it checks every single element, even those not on any diagonal.
### Explanation
The algorithm uses two nested loops to traverse each cell `(i, j)` of the matrix. Inside the loops, a condition checks if the cell is part of a diagonal. A cell `mat[i][j]` is on the primary diagonal if its row index `i` is equal to its column index `j` (`i == j`). A cell is on the secondary diagonal if the sum of its indices equals `n - 1` (`i + j == n - 1`). If either of these conditions is true, the element's value is added to the `sum`. The `OR` condition (`||`) naturally handles the case of the central element (in odd-sized matrices) by ensuring it's added only once. After iterating through all elements, the final `sum` is returned.

```java
class Solution {
    public int diagonalSum(int[][] mat) {
        int n = mat.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // Check for primary diagonal or secondary diagonal
                if (i == j || i + j == n - 1) {
                    sum += mat[i][j];
                }
            }
        }
        return sum;
    }
}
```
### Algorithm
- Initialize a variable `sum` to 0.
- Get the dimension of the square matrix, `n`.
- Use nested loops to iterate from `i = 0` to `n-1` and `j = 0` to `n-1`.
- Inside the inner loop, check if `i == j` (primary diagonal) or `i + j == n - 1` (secondary diagonal).
- If the condition is true, add `mat[i][j]` to `sum`.
- Return `sum`.

## Single Pass Iteration with Correction
A more efficient approach is to iterate only once from `i = 0` to `n-1`. In each iteration, we can access both the primary and secondary diagonal elements corresponding to the current row `i` and sum them up. A final correction is made for odd-sized matrices.
**Time:** O(n), where `n` is the number of rows. We iterate through the rows only once. · **Space:** O(1), as we only use a constant amount of extra space.
**Pros:** Much more efficient than the O(n^2) approach.; Simple logic.
**Cons:** Requires a final correction step for odd-sized matrices.
### Explanation
This method avoids iterating through the entire matrix. Instead, it uses a single loop that runs `n` times. In each iteration `i`, we add the element from the primary diagonal, `mat[i][i]`, to our sum. Simultaneously, we add the element from the secondary diagonal, `mat[i][n - 1 - i]`. This process correctly sums all diagonal elements. However, for matrices with an odd dimension `n`, the center element `mat[n/2][n/2]` is part of both diagonals and gets added twice. To correct this, after the loop finishes, we check if `n` is odd. If it is, we subtract the value of the center element, which was double-counted.

```java
class Solution {
    public int diagonalSum(int[][] mat) {
        int n = mat.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            // Add element from primary diagonal
            sum += mat[i][i];
            // Add element from secondary diagonal
            sum += mat[i][n - 1 - i];
        }
        // If n is odd, the center element is counted twice.
        // We need to subtract it once.
        if (n % 2 != 0) {
            sum -= mat[n / 2][n / 2];
        }
        return sum;
    }
}
```
### Algorithm
- Initialize a variable `sum` to 0.
- Get the dimension of the square matrix, `n`.
- Loop from `i = 0` to `n-1`.
- In each iteration, add the primary diagonal element `mat[i][i]` to `sum`.
- Also, add the secondary diagonal element `mat[i][n - 1 - i]` to `sum`.
- After the loop, check if `n` is odd (`n % 2 != 0`).
- If `n` is odd, subtract the central element `mat[n/2][n/2]` from `sum` to correct for double-counting.
- Return `sum`.

## Optimized Single Pass Iteration
This is a slight refinement of the single-pass approach. Instead of adding both diagonal elements and then subtracting the center if necessary, we can use a conditional check within the loop to avoid double-counting from the start.
**Time:** O(n), where `n` is the number of rows. The single loop runs `n` times. · **Space:** O(1), as we only use a constant amount of extra space.
**Pros:** Highly efficient with O(n) time complexity.; Arguably the cleanest solution as it avoids a separate correction step.
**Cons:** The logic inside the loop is slightly more complex than the previous approach, but it's a minor difference.
### Explanation
This approach also uses a single loop from `i = 0` to `n-1`. In each iteration `i`, we unconditionally add the primary diagonal element `mat[i][i]` to the sum. Then, we check if the primary and secondary diagonal elements for the current row are different. The indices are the same when `i == n - 1 - i`, which only happens for the center element in an odd-sized matrix. If the elements are different (`i != n - 1 - i`), we add the secondary diagonal element `mat[i][n - 1 - i]` to the sum. This way, the center element is considered only once (as part of the primary diagonal addition), and no post-loop correction is needed.

```java
class Solution {
    public int diagonalSum(int[][] mat) {
        int n = mat.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            // Add element from primary diagonal
            sum += mat[i][i];
            
            // Add element from secondary diagonal if it's not the same
            // as the primary diagonal element.
            if (i != n - 1 - i) {
                sum += mat[i][n - 1 - i];
            }
        }
        return sum;
    }
}
```
### Algorithm
- Initialize a variable `sum` to 0.
- Get the dimension of the square matrix, `n`.
- Loop from `i = 0` to `n-1`.
- In each iteration, add the primary diagonal element `mat[i][i]` to `sum`.
- Check if the current row's primary diagonal element is not the same as the secondary diagonal element (i.e., `i != n - 1 - i`).
- If they are not the same element, add the secondary diagonal element `mat[i][n - 1 - i]` to `sum`.
- Return `sum`.

# Solutions
### Java

```java
class Solution { public int diagonalSum ( int [][] mat ) { int ans = 0 ; int n = mat . length ; for ( int i = 0 ; i < n ; ++ i ) { int j = n - i - 1 ; ans += mat [ i ][ i ] + ( i == j ? 0 : mat [ i ][ j ]); } return ans ; } }
```

### CPP

```cpp
class Solution { public: int diagonalSum ( vector < vector < int >>& mat ) { int ans = 0 ; int n = mat . size (); for ( int i = 0 ; i < n ; ++ i ) { int j = n - i - 1 ; ans += mat [ i ][ i ] + ( i == j ? 0 : mat [ i ][ j ]); } return ans ; } };
```

### Python

```python
class Solution : def diagonalSum ( self , mat : List [ List [ int ]]) -> int : ans = 0 n = len ( mat ) for i , row in enumerate ( mat ): j = n - i - 1 ans += row [ i ] + ( 0 if j == i else row [ j ]) return ans
```