Leetcode – Matrix Diagonal Sum Solution

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:

1. Initialize a variable result to 0.
2. Iterate through each element on the primary diagonal, adding them to result.
3. Iterate through each element on the secondary diagonal, adding them to result.
4. 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:

1. Initialize result to 0.
2. Iterate through the matrix in a single pass, adding the diagonal elements to result.
3. 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.