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.
1public class DiagonalSum {
2 public static int diagonalSum(int[][] mat) {
3 int n = mat.length;
4 int sum = 0;
5 for (int i = 0; i < n; i++) {
6 sum += mat[i][i];
7 if (i != n - i - 1) {
8 sum += mat[i][n - i - 1];
9 }
10 }
11 return sum;
12 }
13
14 public static void main(String[] args) {
15 int[][] mat = {
16 {1, 2, 3},
17 {4, 5, 6},
18 {7, 8, 9}
19 };
20 System.out.println(diagonalSum(mat));
21 }
22}This function iterates through the matrix, adding up primary and secondary diagonal elements. It takes care to avoid double-counting the center element in matrices of odd dimensions by checking that indices are not equal for secondary diagonal elements.
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#include <vector>
int diagonalSum(const std::vector<std::vector<int>>& mat) {
int n = mat.size();
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;
}
int main() {
std::vector<std::vector<int>> mat = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
std::cout << diagonalSum(mat) << std::endl;
return 0;
}This C++ solution acknowledges the potential double-counting of the center element during diagonal sum calculation and corrects it after the sum is originally calculated.