Watch 10 video solutions for Matrix Diagonal Sum, a easy level problem involving Array, Matrix. This walkthrough by Knowledge Center has 23,181 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |