Interview Problem Explained: Matrix Diagonal Sum (Array, Matrix)

Matrix Diagonal Sum Problem Statement

Let’s say you are working on an image processing system and are given an N×N pixel matrix mat. Your task is to calculate the sum of the primary diagonal and the secondary diagonal of this matrix.

In some cases, the center pixel (where the diagonals meet) should be counted only once.

Example:

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

• Primary diagonal elements: [1, 5, 9]

• Secondary diagonal elements: [3, 5, 7]

• The center pixel 5 is shared, so we count it only once.

→ Sum: 1 + 5 + 9 + 3 + 7 = 25

This problem tests your ability to design an algorithm that computes the sum of diagonal elements in an N×N square matrix.

While it might look simple enough to solve in one line using static arrays, understanding boundary handling and optimization strategies is key.

Tip: This is LeetCode Problem #1572.
LeetCode’s problem statements are often concise, which can leave some concepts unclear.
Here at Codetree, we break things down with examples and step-by-step guidance for deeper understanding.

Step 1. Naive Approach

Idea

We iterate through every element in the matrix and check if its position (r, c) belongs to the primary or secondary diagonal, then sum it.

Logic Breakdown

1. isPrimaryDiagonal(r, c): r == c

2. isSecondaryDiagonal(n, r, c): r + c == n - 1

3. Use nested for-loops to traverse every (r, c) in the matrix. If either condition is true, add mat[r][c] to the answer.

Related content: Multiples of 2 or 3

Code Implementation

class Solution(object):
    def diagonalSum(self, mat):
        """
        :type mat: List[List[int]]
        :rtype: int
        """
        def isPrimaryDiagonal(r, c):
            return r == c
        
        def isSecondaryDiagonal(n, r, c):
            return r + c == n - 1

        n = len(mat)
        answer = 0
        for r in range(n):
            for c in range(n):
                if isPrimaryDiagonal(r, c) or isSecondaryDiagonal(n, r, c):
                    answer += mat[r][c]
        return answer

Time & Space Complexity

For a matrix of size N×N, we visit each element once, resulting in O(N²) time complexity.

The problem constraints mention N ≤ 100, so an O(N²) solution is acceptable here.

Step 2. Optimizing with Diagonal Indexing

Idea

Once you try Step 1, the next step is to think about making it more efficient. If you directly access only the elements on the primary and secondary diagonals, you can skip unnecessary traversal and improve to O(N).

Note: When the matrix size is odd, the center element belongs to both diagonals, so we need to subtract it once to avoid duplication.

Related problem: Two Line Segments

Logic Breakdown

1. Directly access and sum all elements in the primary diagonal

2. Directly access and sum all elements in the secondary diagonal

3. If the matrix size is odd, subtract the center element once to remove duplication

Code Implementation

class Solution(object):
    def diagonalSum(self, mat):
        """
        :type mat: List[List[int]]
        :rtype: int
        """
        n = len(mat)
        answer = 0
        
        # Primary diagonal
        for r in range(n):
            c = r
            answer += mat[r][c]
        
        # Secondary diagonal
        for r in range(n):
            c = n - r - 1
            answer += mat[r][c]
        
        # Subtract the center if n is odd
        if n % 2 == 1:
            r = n // 2
            c = n // 2
            answer -= mat[r][c]
        
        return answer

Time & Space Complexity

• Time: Two simple loops → O(N)

• Space: No extra space → O(1)

This method offers the most optimal time complexity for this problem.

Frequently Asked Questions

Q. What’s the advantage of using diagonal indexing?

It reduces unnecessary computations and cuts down the overall operation count from O(N²) to O(N).
It also allows you to clearly express the diagonal elements using simple formulas, making your code cleaner and easier to read.

Q. Why do we subtract the center element when the matrix size is odd?

In odd-sized matrices, the primary and secondary diagonals meet at the center.
For example, in a 3×3 matrix, (1, 1) belongs to both diagonals and would otherwise be double-counted. We subtract it once to correct that.

Q. How do you differentiate between the primary and secondary diagonals?

Using the index (r, c):

• Primary diagonal: r == c

• Secondary diagonal: r + c == n - 1

How to Prepare for Interviews with the "Matrix Diagonal Sum" Problem

The 'Matrix Diagonal Sum' problem is a great example to practice 2D array traversal and conditional logic using index patterns. It helps you get familiar with handling edge cases like overlaps in square matrices. In interviews, problems like this often serve as a foundation for more advanced matrix manipulation questions.

This problem boosts your skills in:

• Using nested loops for 2D array traversal

• Writing clean conditional logic for diagonals (r == c, r + c == n - 1)

• Handling duplication when working with odd-sized matrices

Similar Problems to Practice

• 867. Transpose Matrix

• 566. Reshape the Matrix

• Two Line Segments

These are excellent for reinforcing your 2D array traversal and index pattern recognition skills.

How to Review After Solving

1. Write and compare both naive and optimized code:
   Test O(N²) and O(N) solutions side-by-side and measure runtime on small datasets.

2. Practice explaining your logic out loud:
   Get comfortable describing the key logic during a mock interview.

3. Solve at least one related problem:
   Pick from the related problems above and apply your learning right away.