algoadvance

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.

Clarifying Questions

1. What are the primary and secondary diagonals in a square matrix?
   • The primary diagonal of a square matrix runs from the top-left corner to the bottom-right corner.
   • The secondary diagonal runs from the top-right corner to the bottom-left corner.
2. Should we assume the input matrix is always a square matrix (n x n)?
   • Yes, according to the problem statement.
3. What should be the return type?
   • The return type should be an integer representing the sum of the diagonals.
4. Is there any specific constraint on the size of the matrix or the magnitude of its elements?
   • Usually, LeetCode problems conform to reasonable constraints, say n ranges from 1 to 1000, and the element values from -10^5 to 10^5.

Strategy

1. Initialize a variable to keep track of the diagonal sum.
2. Iterate through each row, adding the corresponding elements from the primary and secondary diagonals.
3. Adjust the sum for the middle element if the matrix size is odd, to ensure it is not counted twice.
4. Return the calculated sum.

Code

Here’s the Python function for the described problem:

def diagonalSum(mat):
    n = len(mat)
    total_sum = 0
    
    for i in range(n):
        total_sum += mat[i][i]  # primary diagonal
        total_sum += mat[i][n-1-i]  # secondary diagonal
    
    # If n is odd, we've added the middle element twice, so subtract it once.
    if n % 2 == 1:
        total_sum -= mat[n//2][n//2]
    
    return total_sum

Time Complexity

• Time Complexity: O(n)
  • The function iterates through each row of the matrix exactly once, leading to a linear time complexity with respect to the number of rows (or columns) in the matrix.
• Space Complexity: O(1)
  • The function uses a constant amount of additional space regardless of the input size.

This solution ensures an efficient and straightforward approach to summing up the diagonal elements of a square matrix.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?