LeetCode 1572 - Matrix Diagonal Sum

The problem gives us a square matrix mat of size n x n. A square matrix means the number of rows and columns are the sam

leetcodeeasyarraymatrix

LeetCode Problem 1572

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

The problem gives us a square matrix mat of size n x n. A square matrix means the number of rows and columns are the same. We must calculate the sum of all elements that belong to either of the two diagonals.

The primary diagonal contains elements where the row index and column index are equal:

mat[i][i]

For example, in a 3 x 3 matrix, the primary diagonal positions are:

(0,0), (1,1), (2,2)

The secondary diagonal contains elements where the row index and column index add up to n - 1:

mat[i][n - 1 - i]

For a 3 x 3 matrix, the secondary diagonal positions are:

(0,2), (1,1), (2,0)

The important detail is that if an element belongs to both diagonals, it must only be counted once. This only happens in matrices with odd dimensions, where the center element lies on both diagonals.

The input is a two-dimensional integer array representing the matrix. The output is a single integer representing the total diagonal sum.

The constraints are relatively small:

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

Since the matrix size is at most 100 x 100, even an O(n²) solution is fast enough. However, the structure of the diagonals allows us to do better with a direct traversal.

Several edge cases are important:

  • A 1 x 1 matrix contains only one element, which belongs to both diagonals. It must only be counted once.
  • Odd-sized matrices have a shared center element.
  • Even-sized matrices do not have overlapping diagonals.
  • A naive implementation may accidentally double count the center element.

Approaches

Brute Force Approach

A straightforward approach is to iterate through every element in the matrix and determine whether it belongs to either diagonal.

For every position (i, j):

  • It belongs to the primary diagonal if i == j
  • It belongs to the secondary diagonal if i + j == n - 1

If either condition is true, we add the value to the answer.

This approach is correct because every matrix element is checked exactly once, and we only include values that lie on one or both diagonals.

The time complexity is O(n²) because we scan the entire matrix. Although this is acceptable for the given constraints, it is unnecessary because only 2n positions are relevant.

Optimal Approach

The key observation is that we never need to inspect the entire matrix. The diagonal positions can be computed directly.

For each row i:

  • The primary diagonal element is mat[i][i]
  • The secondary diagonal element is mat[i][n - 1 - i]

We can add both values during a single loop over all rows.

However, for odd-sized matrices, the center element appears in both diagonals. To avoid double counting, we subtract the center element once after the loop.

This reduces the traversal to only n iterations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Scans every matrix cell and checks diagonal conditions
Optimal O(n) O(1) Directly accesses diagonal elements only

Algorithm Walkthrough

  1. Initialize a variable total_sum to 0.

This variable stores the running total of all diagonal elements. 2. Determine the matrix size n.

Since the matrix is square, n = len(mat) gives both the number of rows and columns. 3. Iterate through each row index i from 0 to n - 1.

During each iteration:

  • Add the primary diagonal value:
mat[i][i]
  • Add the secondary diagonal value:
mat[i][n - 1 - i]
  1. Check whether the matrix size is odd.

If n is odd, then the center element belongs to both diagonals and has been counted twice. 5. Subtract the center element once.

The center index is:

n // 2

So we subtract:

mat[n // 2][n // 2]
  1. Return total_sum.

Why it works

For every row i, there is exactly one primary diagonal element and one secondary diagonal element. The algorithm visits all such positions directly, so every diagonal element is included.

In odd-sized matrices, the center element satisfies both diagonal conditions simultaneously. Since the algorithm adds both diagonals independently, the center is counted twice. Subtracting it once restores the correct total.

Therefore, the algorithm always produces the correct diagonal sum.

Python Solution

from typing import List

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        n = len(mat)
        total_sum = 0

        for i in range(n):
            total_sum += mat[i][i]
            total_sum += mat[i][n - 1 - i]

        if n % 2 == 1:
            center = n // 2
            total_sum -= mat[center][center]

        return total_sum

The implementation begins by determining the matrix size n. A variable named total_sum stores the running answer.

The loop iterates through every row index i. During each iteration, the code directly accesses both diagonal positions:

mat[i][i]

and

mat[i][n - 1 - i]

This avoids scanning unnecessary cells.

After the loop, the implementation checks whether n is odd. If it is, the center element was added twice because both diagonal formulas point to the same position. The code subtracts that value once to correct the result.

Finally, the method returns the computed sum.

Go Solution

func diagonalSum(mat [][]int) int {
    n := len(mat)
    totalSum := 0

    for i := 0; i < n; i++ {
        totalSum += mat[i][i]
        totalSum += mat[i][n-1-i]
    }

    if n%2 == 1 {
        center := n / 2
        totalSum -= mat[center][center]
    }

    return totalSum
}

The Go implementation follows the same logic as the Python solution. Slices are used to represent the matrix, and indexing works similarly.

There are no integer overflow concerns because the maximum possible sum is very small:

2 * 100 * 100 = 20000

which easily fits within Go's int type.

Go does not require explicit handling for empty matrices because the constraints guarantee n >= 1.

Worked Examples

Example 1

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

Primary diagonal:

1 + 5 + 9

Secondary diagonal:

3 + 5 + 7

The center element 5 overlaps.

i Primary Value Secondary Value Running Sum
0 1 3 4
1 5 5 14
2 9 7 30

Since n = 3 is odd:

Subtract center element = 5

Final answer:

30 - 5 = 25

Example 2

mat = [
    [1,1,1,1],
    [1,1,1,1],
    [1,1,1,1],
    [1,1,1,1]
]
i Primary Value Secondary Value Running Sum
0 1 1 2
1 1 1 4
2 1 1 6
3 1 1 8

Since n = 4 is even, there is no overlap.

Final answer:

8

Example 3

mat = [[5]]
i Primary Value Secondary Value Running Sum
0 5 5 10

Since n = 1 is odd:

Subtract center element = 5

Final answer:

10 - 5 = 5

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass through all rows, with constant work per row
Space O(1) Only a few variables are used

The algorithm performs exactly one loop over the matrix rows. Each iteration accesses two matrix elements directly, so the total work grows linearly with n.

No additional data structures are allocated, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        n = len(mat)
        total_sum = 0

        for i in range(n):
            total_sum += mat[i][i]
            total_sum += mat[i][n - 1 - i]

        if n % 2 == 1:
            center = n // 2
            total_sum -= mat[center][center]

        return total_sum

solution = Solution()

assert solution.diagonalSum([[1,2,3],[4,5,6],[7,8,9]]) == 25  # odd-sized matrix with overlap
assert solution.diagonalSum([[1,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1]]) == 8  # even-sized matrix
assert solution.diagonalSum([[5]]) == 5  # single-element matrix
assert solution.diagonalSum([[1,2],[3,4]]) == 10  # smallest even matrix
assert solution.diagonalSum([[7,0,0],[0,8,0],[0,0,9]]) == 24  # diagonal-heavy matrix
assert solution.diagonalSum([[1,0,1],[0,1,0],[1,0,1]]) == 5  # overlapping center element
assert solution.diagonalSum([[100]]) == 100  # maximum value in smallest matrix
assert solution.diagonalSum([
    [1,2,3,4,5],
    [6,7,8,9,10],
    [11,12,13,14,15],
    [16,17,18,19,20],
    [21,22,23,24,25]
]) == 117  # larger odd-sized matrix
Test Why
[[1,2,3],[4,5,6],[7,8,9]] Validates odd-sized overlap handling
4 x 4 all ones matrix Verifies even-sized matrices have no overlap
[[5]] Tests smallest possible input
[[1,2],[3,4]] Tests smallest even-sized matrix
Diagonal-heavy matrix Ensures only diagonal elements are counted
Sparse 3 x 3 matrix Confirms center is not double counted
[[100]] Tests maximum cell value in minimal size
Larger 5 x 5 matrix Verifies correctness on larger odd dimensions

Edge Cases

One important edge case is a matrix of size 1 x 1. In this situation, the only element belongs to both diagonals simultaneously. A careless implementation might add it twice and return an incorrect result. This solution handles the case correctly because it subtracts the center element once when the matrix size is odd.

Another important edge case is an odd-sized matrix such as 3 x 3 or 5 x 5. These matrices always contain a center element shared by both diagonals. Without special handling, the center would be double counted. The implementation explicitly checks whether n is odd and removes the duplicate contribution.

Even-sized matrices are also important because they do not contain overlapping diagonals. An incorrect implementation might always subtract a center value regardless of parity. This solution avoids that issue by only subtracting when n % 2 == 1.

A final edge case involves matrices where non-diagonal values are large or distracting. A brute-force implementation with incorrect conditions could accidentally include off-diagonal elements. This implementation avoids that risk entirely because it computes diagonal indices directly rather than checking every matrix position.