Scale Engineer

Matrix Diagonal Sum

Easy
#1446Time: 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.
Data structures
ArrayMatrix

Prompt

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].length
  • 1 <= n <= 100
  • 1 <= 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 sum to 0.
  • Get the dimension of the square matrix, n.
  • Use nested loops to iterate from i = 0 to n-1 and j = 0 to n-1.
  • Inside the inner loop, check if i == j (primary diagonal) or i + j == n - 1 (secondary diagonal).
  • If the condition is true, add mat[i][j] to sum.
  • 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.

Solutions

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 ; } }

Video 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.

← Previous

Previous problem

Next →

Next problem