easy Problem 2 Matrix Diagonal Sum

Problem Statement

Given a square matrix (2D array), calculate the sum of its two diagonals.

The two diagonals in consideration are the primary diagonal that spans from the top-left to the bottom-right and the secondary diagonal that spans from top-right to bottom-left. If a number is part of both diagonals (which occurs only for odd-sized matrices), it should be counted only once in the sum.

Examples

1. Example 1:
   • Input:

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

   • Expected Output: 25
   • Justification: Summing up the two diagonals (1+5+9+3+7), we get 25. Please note that the element at [1][1] = 5 is counted only once.
2. Example 2:
   • Input:

     [[1,0],
      [0,1]]
     

   • Expected Output: 2
   • Justification: The sum of the two diagonals is 1+1 = 2.
3. Example 3:
   • Input:

     [[5]]
     

   • Expected Output: 5
   • Justification: Since there's only one element, it is the sum itself.

Constraints:

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

Pattern

Index arithmetic on a square matrix. Primary diagonal: mat[i][i]. Secondary: mat[i][n-1-i]. When n is odd the center mat[n/2][n/2] lies on both diagonals — add both legs then subtract the center once, or skip the secondary add when i == n-1-i. One loop over i ∈ [0,n) is O(n), not O(n²): you never touch off-diagonal cells.

Solution

One loop accumulates primary and secondary diagonal entries. If n is odd, subtract the center after the loop so it is counted only once. This visits 2n (or 2n−1) cells — linear in the side length.

Step-by-Step Algorithm

1. Initialize Sum: Start by initializing a variable to store the sum of the diagonal elements. Let's call this variable diagonalSum.

2. Loop Through Matrix: Iterate through the matrix using a loop. Since the matrix is square, you can use a single index to traverse both rows and columns. Let's use i as the loop variable, ranging from 0 to the length of the matrix minus one.

3. Add Primary Diagonal Elements: In each iteration, add the element at the primary diagonal to diagonalSum. The primary diagonal elements are those where the row and column indices are equal, i.e., matrix[i][i].

4. Add Secondary Diagonal Elements: In the same iteration, add the element at the secondary diagonal to diagonalSum. The secondary diagonal elements are those where the column index is the complement of the row index, i.e., matrix[i][matrix.length - 1 - i].

5. Avoid Double Counting: If the matrix has an odd number of rows and columns, the central element will be counted twice (once for each diagonal). To correct this, subtract the central element from diagonalSum. The central element is at the position matrix[middle][middle], where middle = matrix.length / 2.

6. Return the Result: After completing the loop, return the value of diagonalSum. This is the sum of the elements on both diagonals of the matrix.

Algorithm Walkthrough

• Initialize totalSum to 0.
• Loop i from 0 to n-1 (inclusive). Where n is the size of the matrix (3 in this example).
  • Add mat[i][i] and mat[i][n-i-1] to totalSum.
  • For i=0, add 1+3 to totalSum => totalSum = 4.
  • For i=1, add 5+5 to totalSum => totalSum = 14.
  • For i=2, add 9+7 to totalSum => totalSum = 30.
• Since n is odd, subtract the central element mat[n/2][n/2] (which is 5) from totalSum to correct for double-counting => totalSum = 25.
• Return totalSum which is 25.

Code

Here is the code for this algorithm:

Complexity Analysis

Time Complexity

• Single loop over rows: The algorithm iterates over the matrix once, accessing the elements on both the primary and secondary diagonals. Since the matrix is n x n, the loop runs times, where n is the number of rows (or columns) in the matrix.

• Additional operations: For each row, two elements are accessed and added (one from the primary diagonal and one from the secondary diagonal), which are constant time operations, .

• Therefore, the total time complexity is .

Overall time complexity: .

Space Complexity

• Constant space: The algorithm uses only a few extra variables (n, totalSum), which require constant space. No additional data structures are used that depend on the input size.

Overall space complexity: .

🎯 STRICT STANDOUT: Why / complexity derivation / pattern+when-not / edges / drills — Solution Matrix Diagonal Sum (easy)

Why this exists (judgment layer)

Index arithmetic beats scanning the whole matrix: only 2n−1 cells matter. The odd-n center double-count is the classic off-by-one trap.

Worked example & complexity derivation

mat 3×3: [[1,2,3],[4,5,6],[7,8,9]]
i=0: +1 +3 → 4
i=1: +5 +5 → 14  (center twice)
i=2: +9 +7 → 30
n odd → subtract mat[1][1]=5 → 25
Primary mat[i][i]; secondary mat[i][n-1-i]; skip secondary if i==n-1-i
Time O(n) not O(n²); space O(1)
Even n=2: [[1,0],[0,1]] → 1+0 + 0+1 = 2, no center subtract

Pattern transfer & when-NOT

Pattern: INDEX ARITHMETIC on square matrix diagonals. When-NOT: non-square (problem requires square); sum all anti-diagonals of every length → different loop; need list of diagonal values not sum → collect instead of add.

Edge cases (hand-run)

n=1 → mat[0][0] once. Even n → no double center. Verify walkthrough 30−5=25 for 3×3 example.

Hostile-panel drills (defend the decision)

Q1. Why not O(n²)?
Model answer: Only diagonal cells are read; off-diagonals never visited — loop is n iterations of O(1).

Q2. Two ways to avoid double-counting the center?
Model answer: (1) Add both legs then subtract center if n odd. (2) When adding secondary, skip if i==n-1-i.

Q3. Hand-run n=1 and n=2.
Model answer: [[5]]→5. [[1,0],[0,1]]→2.