We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Matrix Diagonal Sum

Number: 1677

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Adobe, Yandex

Problem Description

Given a square matrix, return the sum of its diagonals. The primary diagonal consists of elements located at (i, i), and the secondary diagonal consists of elements at (i, n-1-i). If an element appears in both diagonals (as in the center of an odd-sized matrix), it should only be counted once.

Key Insights

  • Iterate through the matrix using a single loop.
  • Add the primary diagonal element at (i, i) for each row.
  • Add the secondary diagonal element at (i, n-1-i) if it is different from the primary diagonal element.
  • Ensure that the center element in an odd-length matrix is not double-counted.

Space and Time Complexity

Time Complexity: O(n), where n is the number of rows (or columns) in the matrix.
Space Complexity: O(1), as no extra space is used aside from a few variables.

Solution

We iterate over each row of the matrix. For each index i, we add the element from the primary diagonal, mat[i][i]. Then, we add the element from the secondary diagonal, mat[i][n-1-i], if it does not coincide with the primary diagonal element (which happens when i equals n-1-i). This simple traversal guarantees that every required element is added exactly once. The algorithm uses a single loop with constant additional space, ensuring optimal performance.

Code Solutions

def diagonalSum(mat):
    # Determine the size of the matrix
    n = len(mat)
    total = 0
    # Loop over each row index
    for i in range(n):
        # Add the primary diagonal element
        total += mat[i][i]
        # Add the secondary diagonal element if it's not the same as the primary
        if i != n - 1 - i:
            total += mat[i][n - 1 - i]
    return total

# Example usage:
matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]
print(diagonalSum(matrix))  # Output: 25
← Back to All Questions