Matrix Diagonal Sum - Solution & Explanation
Problem Statement
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] <= 100
Approach Overview
Problem 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.
Approach 1: Iterative Approach
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.
Complexity
Time Complexity: O(n) since we traverse the matrix diagonals once.
Space Complexity: O(1) as we use a constant amount of extra space.
Approach 2: Pre-calculation for Middle Element
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.
Complexity
Time Complexity: O(n) because of the loop through the matrix diagonals.
Space Complexity: O(1) as we use constant additional space.
Approach 3: Row-by-Row Traversal
We can traverse each row row[i] of the matrix. For each row, we calculate the elements on the two diagonals, i.e., row[i][i] and row[i][n - i - 1], where n is the number of rows in the matrix. If i = n - i - 1, it means there is only one element on the diagonals of the current row; otherwise, there are two elements. We add these elements to the answer.
After traversing all rows, we get the answer.
The time complexity is O(n), where n is the number of rows in the matrix. The space complexity is O(1).
Complexity Comparison
| 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. |
| Row-by-Row Traversal | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Matrix Diagonal Sum | LeetCode 1572 | C++, Java, Python • Knowledge Center • 23,217 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Matrix Diagonal Sum easy or hard?
Matrix Diagonal Sum Python/Java solution
How to solve Matrix Diagonal Sum in O(n)?
What is the best approach for Matrix Diagonal Sum?
Is Matrix Diagonal Sum asked at Google/Amazon/Meta?
What data structure is used in Matrix Diagonal Sum?
What is the time complexity of Matrix Diagonal Sum?
Ready to solve this problem?
Practice Matrix Diagonal Sum with our built-in code editor and test cases.
Practice on FleetCode