Matrix Diagonal Sum - Leetcode Solution

Matrix Diagonal Sum is a problem on Leetcode that requires finding the sum of the elements present in the diagonal of a square matrix. The task is to find the sum of elements present in the main diagonal, i.e., from the top-left corner to the bottom-right corner of the matrix, as well as the other diagonal, i.e., from the top-right corner to the bottom-left corner of the matrix.

Let's take a square matrix of size n x n as an input. The matrix can be represented by a two-dimensional array. We can calculate the sum of elements in the main diagonal by iterating over the rows and columns of the matrix and adding the value of elements whose row and column index is the same. Similarly, we can calculate the sum of elements in the other diagonal by iterating over the rows and columns of the matrix and adding the value of elements whose row index is the same as the difference between the column index and the size of the matrix minus one.

Here is the detailed solution for the Matrix Diagonal Sum problem on Leetcode:

Algorithm:

1. Initialize two variables, main_diagonal_sum and other_diagonal_sum, to zero.
2. Traverse the matrix row-wise and column-wise using two nested loops.
3. For the main diagonal, if the row index is equal to the column index, add the element to the main_diagonal_sum.
4. For the other diagonal, if the row index is equal to the size of the matrix minus one minus the column index, add the element to the other_diagonal_sum.
5. After completing the traversal, return the sum of main_diagonal_sum and other_diagonal_sum.

Python Code:

def diagonalSum(mat):
    n = len(mat)
    main_diagonal_sum = other_diagonal_sum = 0

    for i in range(n):
        main_diagonal_sum += mat[i][i]
        other_diagonal_sum += mat[i][n-i-1]

    return main_diagonal_sum + other_diagonal_sum

Time Complexity: O(n) where n is the size of the matrix.

Space Complexity: O(1) since only two variables are required to store the sum of elements.

1