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.
Link: https://leetcode.com/problems/matrix-diagonal-sum/
Problem Explanation with examples:-
Example 1
Input: mat = [[1,2,3],
[4,5,6],
[7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.
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
Constraints
n == mat.length == mat[i].length1 <= n <= 1001 <= mat[i][j] <= 100
Intuition:-
As, it is a square matrix, the sum of the diagonal elements will be the sum of the elements at the indices (0,0), (1,1), (2,2), ..., (n-1,n-1) and (0,n-1), (1,n-2), (2,n-3), ..., (n-1,0).
So, we can keep two pointers, one at (0,0) and the other at (0,n-1), and iterate over the matrix and keep moving the pointers towards each other.
If the pointers are not at the same index, add the elements at the indices pointed by the pointers to the sum. Else, add the element at the index pointed by any of the pointers to the sum.
Return the sum.
Solution:-
Initialize a variable sm to 0.
Initialize two variables a and b to 0 and n-1 respectively, where n is the number of rows or columns in the matrix.
Iterate over the matrix and add the elements at the indices pointed by the pointers a and b to the sum sm.
Increment a and decrement b.
Return sm.
Code:-
JAVA Solution
class Solution {
public int diagonalSum(int[][] mat) {
int n = mat.length;
int sm = 0;
int a = 0;
int b = n-1;
for(int i = 0;i < n; i++){
if(a != b)
sm += (mat[i][a] + mat[i][b]);
else
sm += (mat[i][a]);
a++;
b--;
}
return sm;
}
}
Python Solution
class Solution:
def diagonalSum(self, mat: List[List[int]]) -> int:
n = len(mat)
sm = 0
a = 0
b = n-1
for i in range(n):
if a != b:
sm += (mat[i][a] + mat[i][b])
else:
sm += (mat[i][a])
a += 1
b -= 1
return sm
Complexity Analysis:-
TIME:-
The time complexity is O(n) as we are iterating only over the rows of the matrix.
SPACE:-
The space complexity is O(1) as we are not using any extra space.