algoadvance

Leetcode 1572. Matrix Diagonal Sum

Problem Statement

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.

Clarifying Questions

  1. What is the definition of the primary and secondary diagonals?
    • Primary Diagonal: Consists of elements where the row index is equal to the column index (mat[i][i]).
    • Secondary Diagonal: Consists of elements where the row index and column index sum to n-1 (mat[i][n-i-1]).
  2. What are the constraints?
    • The matrix is guaranteed to be square (i.e., the number of rows equals the number of columns).
    • Elements in the matrix can be negative.
  3. Examples:
    • For a 3x3 matrix: 
      1 2 3
4 5 6
7 8 9

      The sum should be: 1 + 5 + 9 (primary diagonal) + 3 + 7 (secondary diagonal, excluding the center element 5) = 1 + 5 + 9 + 3 + 7 = 25.

Strategy

  1. Initialize a variable to accumulate the sum.
  2. Iterate over the range from 0 to n-1 (where n is the number of rows/columns in the square matrix).
  3. For each index i within the range, add mat[i][i] (primary diagonal element) to the sum.
  4. Add mat[i][n-i-1] (secondary diagonal element) to the sum.
  5. If the current element belongs to both primary and secondary diagonals (i.e., i == n-i-1), subtract that element from the sum once to avoid double-counting.
  6. Finally, return the accumulated sum.

Code

public class Solution {
    public int diagonalSum(int[][] mat) {
        int n = mat.length;
        int sum = 0;
        
        for (int i = 0; i < n; i++) {
            // Add the primary diagonal element
            sum += mat[i][i];
            // Add the secondary diagonal element
            sum += mat[i][n - i - 1];
        }
        
        // If the matrix has an odd dimension, subtract the center element once if it was added twice
        if (n % 2 == 1) {
            sum -= mat[n / 2][n / 2];
        }
        
        return sum;
    }
}

Time Complexity

Feel free to ask any further questions or for additional clarifications!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI