Matrix Diagonal Sum
EasyPrompt
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: 8Example 3:
Input: mat = [[5]]
Output: 5
Constraints:
n == mat.length == mat[i].length1 <= n <= 1001 <= mat[i][j] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through every element of the n x n matrix. For each element, we check if it lies on the primary or secondary diagonal. If it does, we add its value to a running total.
Algorithm
- Initialize a variable
sumto 0. - Get the dimension of the square matrix,
n. - Use nested loops to iterate from
i = 0ton-1andj = 0ton-1. - Inside the inner loop, check if
i == j(primary diagonal) ori + j == n - 1(secondary diagonal). - If the condition is true, add
mat[i][j]tosum. - Return
sum.
Walkthrough
The algorithm uses two nested loops to traverse each cell (i, j) of the matrix. Inside the loops, a condition checks if the cell is part of a diagonal. A cell mat[i][j] is on the primary diagonal if its row index i is equal to its column index j (i == j). A cell is on the secondary diagonal if the sum of its indices equals n - 1 (i + j == n - 1). If either of these conditions is true, the element's value is added to the sum. The OR condition (||) naturally handles the case of the central element (in odd-sized matrices) by ensuring it's added only once. After iterating through all elements, the final sum is returned.
class Solution { public int diagonalSum(int[][] mat) { int n = mat.length; int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Check for primary diagonal or secondary diagonal if (i == j || i + j == n - 1) { sum += mat[i][j]; } } } return sum; }}Complexity
Time
O(n^2), where `n` is the number of rows (or columns) in the matrix. We visit every element in the matrix.
Space
O(1), as we only use a constant amount of extra space for the `sum` variable and loop counters.
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient for large matrices as it checks every single element, even those not on any diagonal.
A more efficient approach is to iterate only once from i = 0 to n-1. In each iteration, we can access both the primary and secondary diagonal elements corresponding to the current row i and sum them up. A final correction is made for odd-sized matrices.
Algorithm
- Initialize a variable
sumto 0. - Get the dimension of the square matrix,
n. - Loop from
i = 0ton-1. - In each iteration, add the primary diagonal element
mat[i][i]tosum. - Also, add the secondary diagonal element
mat[i][n - 1 - i]tosum. - After the loop, check if
nis odd (n % 2 != 0). - If
nis odd, subtract the central elementmat[n/2][n/2]fromsumto correct for double-counting. - Return
sum.
Walkthrough
This method avoids iterating through the entire matrix. Instead, it uses a single loop that runs n times. In each iteration i, we add the element from the primary diagonal, mat[i][i], to our sum. Simultaneously, we add the element from the secondary diagonal, mat[i][n - 1 - i]. This process correctly sums all diagonal elements. However, for matrices with an odd dimension n, the center element mat[n/2][n/2] is part of both diagonals and gets added twice. To correct this, after the loop finishes, we check if n is odd. If it is, we subtract the value of the center element, which was double-counted.
class Solution { public int diagonalSum(int[][] mat) { int n = mat.length; int sum = 0; for (int i = 0; i < n; i++) { // Add element from primary diagonal sum += mat[i][i]; // Add element from secondary diagonal sum += mat[i][n - 1 - i]; } // If n is odd, the center element is counted twice. // We need to subtract it once. if (n % 2 != 0) { sum -= mat[n / 2][n / 2]; } return sum; }}Complexity
Time
O(n), where `n` is the number of rows. We iterate through the rows only once.
Space
O(1), as we only use a constant amount of extra space.
Trade-offs
Pros
Much more efficient than the O(n^2) approach.
Simple logic.
Cons
Requires a final correction step for odd-sized matrices.
This is a slight refinement of the single-pass approach. Instead of adding both diagonal elements and then subtracting the center if necessary, we can use a conditional check within the loop to avoid double-counting from the start.
Algorithm
- Initialize a variable
sumto 0. - Get the dimension of the square matrix,
n. - Loop from
i = 0ton-1. - In each iteration, add the primary diagonal element
mat[i][i]tosum. - Check if the current row's primary diagonal element is not the same as the secondary diagonal element (i.e.,
i != n - 1 - i). - If they are not the same element, add the secondary diagonal element
mat[i][n - 1 - i]tosum. - Return
sum.
Walkthrough
This approach also uses a single loop from i = 0 to n-1. In each iteration i, we unconditionally add the primary diagonal element mat[i][i] to the sum. Then, we check if the primary and secondary diagonal elements for the current row are different. The indices are the same when i == n - 1 - i, which only happens for the center element in an odd-sized matrix. If the elements are different (i != n - 1 - i), we add the secondary diagonal element mat[i][n - 1 - i] to the sum. This way, the center element is considered only once (as part of the primary diagonal addition), and no post-loop correction is needed.
class Solution { public int diagonalSum(int[][] mat) { int n = mat.length; int sum = 0; for (int i = 0; i < n; i++) { // Add element from primary diagonal sum += mat[i][i]; // Add element from secondary diagonal if it's not the same // as the primary diagonal element. if (i != n - 1 - i) { sum += mat[i][n - 1 - i]; } } return sum; }}Complexity
Time
O(n), where `n` is the number of rows. The single loop runs `n` times.
Space
O(1), as we only use a constant amount of extra space.
Trade-offs
Pros
Highly efficient with O(n) time complexity.
Arguably the cleanest solution as it avoids a separate correction step.
Cons
The logic inside the loop is slightly more complex than the previous approach, but it's a minor difference.
Solutions
Solution
class Solution { public int diagonalSum ( int [][] mat ) { int ans = 0 ; int n = mat . length ; for ( int i = 0 ; i < n ; ++ i ) { int j = n - i - 1 ; ans += mat [ i ][ i ] + ( i == j ? 0 : mat [ i ][ j ]); } return ans ; } }class Solution { public: int diagonalSum ( vector < vector < int >>& mat ) { int ans = 0 ; int n = mat . size (); for ( int i = 0 ; i < n ; ++ i ) { int j = n - i - 1 ; ans += mat [ i ][ i ] + ( i == j ? 0 : mat [ i ][ j ]); } return ans ; } };class Solution : def diagonalSum ( self , mat : List [ List [ int ]]) -> int : ans = 0 n = len ( mat ) for i , row in enumerate ( mat ): j = n - i - 1 ans += row [ i ] + ( 0 if j == i else row [ j ]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.