#1572

Easy

LeetCode Problem Workspace

Matrix Diagonal Sum

Calculate the sum of both primary and secondary diagonals in a square matrix while avoiding double-counting overlaps.

Problem Statement

Given a square matrix mat of size n x n, calculate the sum of all elements on both the primary diagonal and the secondary diagonal. If an element belongs to both diagonals, count it only once.

Return the total sum of these diagonal elements. For example, in mat = [[1,2,3],[4,5,6],[7,8,9]], the sum of diagonals is 1 + 5 + 9 + 3 + 7 = 25, where the center element 5 is counted only once.

Examples

Example 1

Input: mat = [[1,2,3], [4,5,6], [7,8,9]]

Output: 25

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 details omitted.

Example 3

Input: mat = [[5]]

Output: 5

Example details omitted.

Constraints

n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100

Solution Approach

Iterate Through Diagonals

Loop over indices i from 0 to n-1. Add mat[i][i] for the primary diagonal and mat[i][n-1-i] for the secondary diagonal, checking if i equals n-1-i to prevent double-counting the center element in odd-length matrices.

Sum Using Single Pass

Use one loop to sum both diagonals in a single iteration to optimize for time. Directly handle overlap for odd-length matrices to ensure each element is counted correctly without extra data structures.

Space Optimization

No additional arrays are required. Store the cumulative sum in a single variable. This leverages O(1) space while maintaining O(n) time, aligning perfectly with the Array plus Matrix pattern for efficient diagonal computations.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because a single loop iterates over n elements. Space complexity is O(1) since only one sum variable is maintained and no extra structures are used.

What Interviewers Usually Probe

Look for an optimized single-pass solution rather than two separate loops.
Check if the candidate handles the overlap of diagonals correctly in odd-length matrices.
Verify understanding of Array plus Matrix access patterns and index calculations.

Common Pitfalls or Variants

Common pitfalls

Double-counting the central element when n is odd.
Iterating over extra loops unnecessarily instead of combining diagonal sums in one pass.
Miscalculating secondary diagonal indices, especially off-by-one errors.

Follow-up variants

Calculate diagonal sums for rectangular matrices, summing only valid diagonal elements.
Return the sum of diagonals excluding elements greater than a threshold value.
Compute the difference between primary and secondary diagonal sums for analysis.

FAQ

How do I handle the center element in an odd-length matrix for Matrix Diagonal Sum?

Check if the current index i equals n-1-i during iteration. If so, add the element only once to prevent double-counting the center.

Can this solution work for non-square matrices?

No, the standard approach assumes a square matrix where primary and secondary diagonals are defined. Rectangular matrices require adjusted diagonal definitions.

What is the time complexity pattern for summing diagonals in this problem?

It follows the Array plus Matrix pattern: a single pass over n elements per diagonal, yielding O(n) time complexity with O(1) extra space.

Why not use separate loops for each diagonal?

Separate loops increase code complexity and risk double-counting. Combining sums in one loop ensures correctness and efficiency.

Is extra space needed to track visited elements?

No. By handling overlap through index comparison, the solution uses only a single sum variable, maintaining O(1) space.

terminal

Solution

Solution 1: Row-by-Row Traversal

We can traverse each row $\textit{row}[i]$ of the matrix. For each row, we calculate the elements on the two diagonals, i.e., $\textit{row}[i][i]$ and $\textit{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.

1

2

3

4

5

6

7

8

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 ans

Continue Practicing

#1568 minimum number of days to disconnect island #1582 special positions in a binary matrix #1559 detect cycles in 2d grid