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.
Example 1:
Input: mat = [[1,2,3], [4,5,6], [7,8,9]] Output: 25 Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25 Notice that element mat[1][1] = 5 is counted only once.
Example 2:
Input: mat = [[1,1,1,1], [1,1,1,1], [1,1,1,1], [1,1,1,1]] Output: 8
Example 3:
Input: mat = [[5]] Output: 5
Constraints:
n == mat.length == mat[i].length1 <= n <= 1001 <= mat[i][j] <= 100This approach involves traversing the matrix and accessing diagonal elements using indices.
Primary Diagonal: For an element to be on the primary diagonal, its row index must be equal to its column index (i.e., mat[i][i]).
Secondary Diagonal: For an element to be on the secondary diagonal, the sum of its row index and column index must be equal to n-1 (i.e., mat[i][n-i-1]).
The function iterates over the elements, and sums those at positions [i][i] for the primary diagonal and [i][n-i-1] for the secondary diagonal. It avoids double-counting the center element in an odd-length matrix.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) since we traverse the matrix diagonals once.
Space Complexity: O(1) as we use a constant amount of extra space.
An alternative method is to calculate both diagonal sums and subtract the repeated center element if it exists. This approaches the same goal in a slightly different way by not thinking too much about the double-count case upfront during the main loop.
This approach calculates the primary and secondary diagonal sums separately. After the sums are obtained, it checks if the matrix is odd in size; if so, it subtracts the middle element from the total sum to correct the double counting.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) because of the loop through the matrix diagonals.
Space Complexity: O(1) as we use constant additional space.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n) since we traverse the matrix diagonals once. |
| Pre-calculation for Middle Element | Time Complexity: O(n) because of the loop through the matrix diagonals. |
Matrix Diagonal Sum | LeetCode 1572 | C++, Java, Python • Knowledge Center • 22,800 views views
Watch 9 more video solutions →Practice Matrix Diagonal Sum with our built-in code editor and test cases.
Practice on FleetCode