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] <= 100Problem Overview: You are given a square n x n matrix. The task is to compute the sum of its primary diagonal (top-left to bottom-right) and secondary diagonal (top-right to bottom-left). If both diagonals overlap at the center element (when n is odd), that value should only be counted once.
Approach 1: Iterative Diagonal Traversal (O(n) time, O(1) space)
Iterate through the matrix using a single loop from i = 0 to n - 1. For each row index i, the primary diagonal element is mat[i][i] and the secondary diagonal element is mat[i][n - i - 1]. Add both values to a running sum while traversing the matrix once. If the matrix size is odd and the iteration reaches the center (i == n - i - 1), add that element only once to avoid double counting.
This method works because both diagonals can be accessed directly using index relationships. The traversal touches exactly n rows, making the time complexity O(n) and extra space O(1). This is the most straightforward and commonly expected solution when working with arrays and matrix traversal problems.
Approach 2: Pre-calculation for Middle Element (O(n) time, O(1) space)
This approach also iterates once through the matrix and sums both diagonals. The difference is that the algorithm first calculates the total of both diagonals without conditions, then adjusts the result afterward. If the matrix size is odd, the center element mat[n/2][n/2] appears in both diagonals and is counted twice. Subtract that value once from the final sum.
The key idea is separating diagonal accumulation from overlap handling. This keeps the loop simpler because every iteration adds both diagonal elements without checking conditions. After traversal, a single adjustment removes the duplicate middle value when needed. Time complexity remains O(n) with constant O(1) space.
Recommended for interviews: The iterative traversal approach with an inline middle check is usually what interviewers expect. It shows you understand diagonal indexing in a square matrix and can prevent double counting during iteration. The post-adjustment method is equally optimal but slightly less explicit about why the overlap occurs.
This 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Diagonal Traversal | O(n) | O(1) | Best general solution. Directly accesses both diagonals during one pass. |
| Pre-calculation for Middle Element | O(n) | O(1) | Useful when you want a simpler loop and handle the center overlap afterward. |
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