1572. Matrix Diagonal Sum
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 77.6%
Problem Breakdown
The problem requires calculating the sum of the primary and secondary diagonals in a square matrix. The primary diagonal consists of elements where the row index equals the column index (e.g., mat[i][i]). The secondary diagonal consists of elements where the row index plus the column index equals the size of the matrix minus one (mat[i][n-i-1]), excluding any overlap with the primary diagonal.
Inputs:
- A square matrix
matof sizen x n.
Outputs:
- An integer representing the sum of the elements on both diagonals, ensuring that any overlapping element (i.e., the center element in odd-sized matrices) is only counted once.
Implicit Constraints or Edge Cases:
- The matrix size
nranges from 1 to 100. - All elements in the matrix are integers between 1 and 100.
- The matrix is guaranteed to be square, so no need to handle non-square matrices.
Intuition
A brute-force approach would involve iterating through each element of the matrix twice: once for the primary diagonal and once for the secondary diagonal. This would result in a time complexity of O(n^2), which is inefficient given that we only need to traverse the diagonals.
The key insight is to recognize that both diagonals can be traversed in a single pass through the matrix, with indices i ranging from 0 to n-1. For each index i, add the element at position (i, i) for the primary diagonal and (i, n-i-1) for the secondary diagonal. If i == n-i-1, it means we are at the center of an odd-sized matrix, so we should only add this element once.
Approach
- Initialize a variable
diagonal_sumto 0. - Iterate through each index
ifrom 0 ton-1. - For each index
i, addmat[i][i]todiagonal_sum(primary diagonal). - Add
mat[i][n-i-1]todiagonal_sum(secondary diagonal). - If
i == n-i-1, subtractmat[i][i]fromdiagonal_sumto avoid double-counting the center element in odd-sized matrices. - Return
diagonal_sum.
Complexity Analysis
- Time Complexity: O(n), where
nis the size of the matrix. We traverse each diagonal once, which takes linear time relative to the number of elements in the matrix. - Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.
Solution
def diagonalSum(mat):
n = len(mat)
diagonal_sum = 0
for i in range(n):
diagonal_sum += mat[i][i] # Primary diagonal
diagonal_sum += mat[i][n-i-1] # Secondary diagonal
if i == n - i - 1:
diagonal_sum -= mat[i][i] # Avoid double-counting the center element
return diagonal_sum
Edge Cases Handled
- Single-element matrix (
n=1): The code correctly sums the single element. - Even-sized matrices: Both diagonals are distinct, so no overlap is handled.
- Odd-sized matrices: The center element is only counted once by checking if
i == n-i-1. - Minimum and maximum constraints: The matrix size and element values are within specified limits, ensuring the solution remains valid.