878381. Diagonal sum
Easy
Diagonal Sum
Slug: diagonal-sum--103215
Difficulty: Easy
Id: 878381
Topic Tags: None
Company Tags: None
Summary
Given a matrix, find the sum of diagonals. A diagonal is any path from top-left to bottom-right or vice versa.
Detailed Explanation
The problem involves finding the sum of the main diagonal (from top-left to bottom-right) and the secondary diagonal (from top-right to bottom-left) in a given matrix. We can solve this by iterating through the matrix, keeping track of the sums for both diagonals, and finally returning their total.
Here's a step-by-step breakdown of the solution:
- Initialize two variables
main_diagonal_sumandsecondary_diagonal_sumto 0. - Iterate through the matrix using nested loops (rows and columns).
- For each element in the matrix:
- If it is on the main diagonal (i.e., its row index equals its column index), add its value to
main_diagonal_sum. - If it is on the secondary diagonal (i.e., its row index plus its column index equals the number of rows minus 1), add its value to
secondary_diagonal_sum.
- If it is on the main diagonal (i.e., its row index equals its column index), add its value to
- Return the sum of
main_diagonal_sumandsecondary_diagonal_sum.
Time complexity: O(n*m) where n is the number of rows and m is the number of columns in the matrix. Space complexity: O(1) as we only use a constant amount of space.
Optimized Solutions
Java
public int diagonalSum(int[][] mat) {
int main_diagonal_sum = 0;
int secondary_diagonal_sum = 0;
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[i].length; j++) {
if (i == j) {
main_diagonal_sum += mat[i][j];
} else if (i + j == mat.length - 1) {
secondary_diagonal_sum += mat[i][j];
}
}
}
return main_diagonal_sum + secondary_diagonal_sum;
}