Matrix Diagonal Sum

Difficulty: Easy | Acceptance: 84.20% | Paid: No Topics: Array, Matrix

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.

• Examples
• Constraints
• Brute Force
• Single Pass Iteration
• Separate Accumulation

Examples

Example 1:

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

Brute Force

Intuition Iterate through every single element in the matrix. Check if the current element lies on the primary diagonal (where row index equals column index) or the secondary diagonal (where row index plus column index equals n - 1). If it does, add it to the sum.

Steps

• Initialize total to 0.
• Get the size of the matrix n.
• Loop through each row i from 0 to n-1.
• Loop through each column j from 0 to n-1.
• Check if i == j (primary diagonal) or i + j == n - 1 (secondary diagonal).
• If either condition is true, add mat[i][j] to total.
• Return total.

class Solution:
    def diagonalSum(self, mat: list[list[int]]) -> int:
        n = len(mat)
        total = 0
        for i in range(n):
            for j in range(n):
                if i == j or i + j == n - 1:
                    total += mat[i][j]
        return total

Complexity

• Time: O(n²) — We visit every element in the n x n matrix.
• Space: O(1) — We only use a constant amount of extra space.
• Notes: Simple to implement but less efficient than necessary since we check every cell.

Single Pass Iteration

Intuition Instead of checking every cell, we can iterate through the rows once. In each row, the primary diagonal element is at index i and the secondary diagonal element is at index n - 1 - i. We add both. If the matrix has an odd size, the center element is added twice (once for each diagonal), so we subtract it once at the end.

Steps

• Initialize total to 0 and n to mat.length.
• Loop i from 0 to n-1.
• Add mat[i][i] (primary diagonal) to total.
• Add mat[i][n - 1 - i] (secondary diagonal) to total.
• If n is odd, subtract mat[n // 2][n // 2] from total to correct the double count.
• Return total.

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

Complexity

• Time: O(n) — We iterate through the matrix rows once.
• Space: O(1) — We only use a constant amount of extra space.
• Notes: Optimal time complexity. The subtraction step handles the overlapping center element efficiently.

Separate Accumulation

Intuition Calculate the sum of the primary diagonal and the sum of the secondary diagonal separately. Then, combine them. If the matrix size is odd, the center element is included in both sums, so we subtract it once from the total.

Steps

• Initialize primarySum, secondarySum, and n.
• Loop i from 0 to n-1.
• Add mat[i][i] to primarySum.
• Add mat[i][n - 1 - i] to secondarySum.
• Calculate total = primarySum + secondarySum.
• If n is odd, subtract mat[n // 2][n // 2] from total.
• Return total.

class Solution:
    def diagonalSum(self, mat: list[list[int]]) -> int:
        n = len(mat)
        primary_sum = 0
        secondary_sum = 0
        
        for i in range(n):
            primary_sum += mat[i][i]
            secondary_sum += mat[i][n - 1 - i]
            
        total = primary_sum + secondary_sum
        
        if n % 2 == 1:
            total -= mat[n // 2][n // 2]
            
        return total

Complexity

• Time: O(n) — We iterate through the matrix rows once.
• Space: O(1) — We use a fixed number of integer variables.
• Notes: Conceptually clear separation of concerns, though functionally similar to the single pass approach.