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.

Example 1:

Input: mat = [[1,2,3],
              [4,5,6],
              [7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25

Example 2:

Input: mat = [[1,1,1,1],
              [1,1,1,1],
              [1,1,1,1],
              [1,1,1,1]]
Output: 8

Example 3:

Input: mat = [[5]]
Output: 5

Clarifying Questions

1. What is the size range of the matrix?
   • You can assume that the matrix size n x n (square matrix) where ( 1 \leq n \leq 100 ).
2. What type of elements will the matrix contain?
   • The elements of the matrix will be integers.
3. What is the expected output?
   • The sum of the primary and secondary diagonal elements, excluding the overlapping element (if it exists).

Strategy

1. Primary Diagonal Sum:
   • For a matrix mat of size n x n, the primary diagonal elements are at positions ((i, i)) for all i from 0 to n-1.
2. Secondary Diagonal Sum:
   • The secondary diagonal elements are at positions ((i, n-1-i)) for all i from 0 to n-1.
3. Overlap Handling:
   • If n is odd, the central element ((n//2, n//2)) will appear in both diagonals. We should subtract this element once if it appears.
4. Edge Cases:
   • For a single element matrix, the primary and secondary diagonal elements are the same.

Code

Here is the implementation in C++:

#include <vector>
using namespace std;

class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int n = mat.size();
        int sum = 0;
        
        for (int i = 0; i < n; ++i) {
            sum += mat[i][i];           // Primary diagonal
            sum += mat[i][n-1-i];       // Secondary diagonal
        }
        
        // If the matrix size is odd, subtract the center element once as it has been added twice.
        if (n % 2 != 0) {
            sum -= mat[n/2][n/2];
        }
        
        return sum;
    }
};

Time Complexity

• The time complexity of this solution is O(n), where n is the number of rows (or columns) in the matrix. This is because we iterate over the matrix diagonals once and perform constant time operations within the loop.

• The space complexity is O(1) as we only use a few auxiliary variables for storing the sum and the loop index.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?