Sponsored
Sponsored
This approach involves traversing the matrix and accessing diagonal elements using indices.
Primary Diagonal: For an element to be on the primary diagonal, its row index must be equal to its column index (i.e., mat[i][i]).
Secondary Diagonal: For an element to be on the secondary diagonal, the sum of its row index and column index must be equal to n-1 (i.e., mat[i][n-i-1]).
Time Complexity: O(n) since we traverse the matrix diagonals once.
Space Complexity: O(1) as we use a constant amount of extra space.
1#include <iostream>
2#include <vector>
3
4int diagonalSum(const std::vector<std::vector<int>>& mat) {
5 int n = mat.size();
6 int sum = 0;
7 for (int i = 0; i < n; i++) {
8 sum += mat[i][i];
9 if (i != n - i - 1) {
10 sum += mat[i][n - i - 1];
11 }
12 }
13 return sum;
14}
15
16int main() {
17 std::vector<std::vector<int>> mat = {
18 {1, 2, 3},
19 {4, 5, 6},
20 {7, 8, 9}
21 };
22 std::cout << diagonalSum(mat) << std::endl;
23 return 0;
24}The solution calculates the sum of diagonals by iterating over the matrix elements. It adds the element at position [i][i] for the primary diagonal and [i][n-i-1] for the secondary diagonal, ignoring the middle element if n is odd.
An alternative method is to calculate both diagonal sums and subtract the repeated center element if it exists. This approaches the same goal in a slightly different way by not thinking too much about the double-count case upfront during the main loop.
Time Complexity: O(n) because of the loop through the matrix diagonals.
Space Complexity: O(1) as we use constant additional space.
1
class Program {
public static int DiagonalSum(int[][] mat) {
int n = mat.Length;
int primarySum = 0, secondarySum = 0;
for (int i = 0; i < n; i++) {
primarySum += mat[i][i];
secondarySum += mat[i][n - i - 1];
}
if (n % 2 == 1) {
primarySum -= mat[n / 2][n / 2];
}
return primarySum + secondarySum;
}
static void Main(string[] args) {
int[][] mat = {
new int[] {1, 2, 3},
new int[] {4, 5, 6},
new int[] {7, 8, 9}
};
Console.WriteLine(DiagonalSum(mat));
}
}The calculation for primary and secondary diagonal sums happens independently, and any repeat of the center element is resolved by subtraction in this C# solution.