1572. Matrix Diagonal Sum
Problem Description
The problem provides us a square matrix mat
, which means the number of rows and columns in the matrix are equal. Our task is to calculate the sum of the diagonal elements, which includes elements from both the primary diagonal and the secondary diagonal. The primary diagonal is the one that starts from the top left corner and ends at the bottom right corner. The secondary diagonal starts from the top right corner and ends at the bottom left corner. However, there's a catch: If any element is common between the primary and secondary diagonals (which would be the case for the central element in a matrix with odd dimensions), we must include it only once in our sum.
Intuition
To approach this problem, we consider the primary and secondary diagonals of the matrix.
-
The primary diagonal elements have the same index for their row and column. In terms of indexes, these are the elements
mat[i][i]
wherei
ranges from 0 to then-1
, whereinn
is the size of one dimension since it's a square matrix. -
The secondary diagonal elements have row and column indexes that sum up to
n-1
. In other words, the indexes are of the formmat[i][j]
wherej
isn-i-1
.
Now, the challenge is to make sure that we don't double-count the element in the case of an odd-dimension matrix where the primary and secondary diagonals intersect. To avoid this, we simply check if the index i
is equal to the index j
. If they are equal, this means we're looking at the central element in the case of an odd-size matrix and we shouldn't add it again.
Therefore, the sum ans
starts at 0, and we iterate through each row with its index i
. While iterating, we calculate j
as n-i-1
for each row to pinpoint the element in the secondary diagonal. We then add to ans
the sum of elements mat[i][i]
and mat[i][j]
, unless i == j
, in which case we only add the element mat[i][i]
once.
By iterating over all rows, we calculate the sum required by the problem without having to deal with two separate loops or maintaining additional data structures, therefore making our approach both efficient and straightforward.
Solution Approach
The solution provided is written in Python and follows a straightforward approach that efficiently computes the sum of the diagonals of a square matrix.
Here's a detailed walkthrough of the implementation:
-
We start by initializing a variable
ans
to 0. This will hold the cumulative sum of the diagonal elements. -
We need the size of the matrix, which is the length of one of its sides (since it is square), so we take the length of the matrix
n = len(mat)
. -
The
for
loop is used to iterate over each row of the matrix. The loop variablei
serves as the index for both rows and the primary diagonal elements.enumerate
is used so we can have both the index and the row elements available during each iteration. -
We then calculate the column index
j
for the secondary diagonal element corresponding to the current row. As explained earlier,j
is given byn - i - 1
. -
Inside the loop, we add to
ans
the value of the primary diagonal elementrow[i]
. -
We also want to add the secondary diagonal element
row[j]
unlessi
is equal toj
(which is the case when we are at the central element of a matrix with an odd number of rows/columns). To do this succinctly, we addrow[j]
only ifj != i
, otherwise, we add0
. This conditional addition is achieved by the expression(0 if j == i else row[j])
. -
After the loop has processed all the rows,
ans
now contains the total sum of both diagonals, with no duplicates for the intersecting element (if any). -
Finally, the method returns the computed
ans
.
There are no complex algorithms, data structures, or patterns involved here. The solution effectively uses index manipulation to address the specific elements required for the sum, making it a simple yet effective approach to solving this problem.
Here is the core logic encapsulated in Python code:
1class Solution:
2 def diagonalSum(self, mat: List[List[int]]) -> int:
3 ans = 0
4 n = len(mat)
5 for i, row in enumerate(mat):
6 j = n - i - 1
7 ans += row[i] + (0 if j == i else row[j])
8 return ans
By carefully choosing and manipulating indexes, we maintain a clear and concise solution without additional memory usage for storing intermediate results or redundant computations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach. Suppose we have the following 3x3 square matrix:
1mat = [ 2 [1, 2, 3], 3 [4, 5, 6], 4 [7, 8, 9] 5]
Here's the step-by-step process of how the solution works:
-
Initialize
ans
to 0. This will keep track of the sum of diagonal elements. -
Determine the size
n
of the matrix. In this case,n = len(mat) = 3
. -
Start the
for
loop withi
iterating from 0 to 2 (since the matrix has 3 rows and columns). -
For each row
i
, calculate the indexj
for accessing the secondary diagonal's element, which isn - i - 1
. This will give us2, 1, 0
fori = 0, 1, 2
respectively. -
Now, add the primary diagonal element to
ans
. In the first iteration withi = 0
, addmat[0][0]
which is1
. -
Check if
i
equalsj
. If they are not the same, add the secondary diagonal element toans
. Withi = 0
andj = 2
, they aren't equal, so addmat[0][2]
which is3
. -
For the second iteration where
i = 1
, we addmat[1][1]
(the middle element) toans
. Sincei
andj
are equal here (both equal to 1), we don't add the secondary diagonal element because that would be double-counting. -
In the third iteration with
i = 2
, add the primary diagonal elementmat[2][2]
which is9
toans
. Indexi
andj
are not the same (becausej = 0
), so add the secondary diagonal elementmat[2][0]
which is7
. -
After adding these elements through the loop, the sum
ans
becomes1 + 3 + 5 + 9 + 7 = 25
. -
The method returns the value of
ans
, which is25
. This is the required sum of the elements on the primary and secondary diagonals of the matrix, without double-counting the center element.
Putting it all into the Python code, we have:
1class Solution:
2 def diagonalSum(self, mat: List[List[int]]) -> int:
3 ans = 0
4 n = len(mat)
5 for i, row in enumerate(mat):
6 j = n - i - 1
7 ans += row[i] + (0 if j == i else row[j])
8 return ans
When we call diagonalSum(mat)
with our example matrix, it will return 25
, which is the correct answer. This demonstrates the efficiency and simplicity of the provided solution approach.
Solution Implementation
1class Solution:
2 def diagonalSum(self, matrix: List[List[int]]) -> int:
3 # Initialize the sum of the diagonals
4 total_sum = 0
5
6 # Get the size of the matrix (assuming it's square)
7 n = len(matrix)
8
9 # Loop over each row and calculate the diagonal sum
10 for i, row in enumerate(matrix):
11 # Calculate the index for the secondary diagonal
12 j = n - i - 1
13 # Add the primary diagonal element
14 total_sum += row[i]
15 # Add the secondary diagonal element if it's not the same as the primary diagonal
16 if j != i:
17 total_sum += row[j]
18
19 # Return the computed sum
20 return total_sum
21
1class Solution {
2 public int diagonalSum(int[][] matrix) {
3 int totalSum = 0; // This will hold the sum of the diagonal elements
4 int size = matrix.length; // The matrix is size x size
5
6 // Loop through each row of the matrix
7 for (int i = 0; i < size; ++i) {
8 int reverseIndex = size - i - 1; // Calculate the corresponding column index for the secondary diagonal
9
10 // Add the primary diagonal element
11 totalSum += matrix[i][i];
12
13 // If it's not the same element (which would be the case in the middle of an odd-sized matrix)
14 // then add the secondary diagonal element
15 if (i != reverseIndex) {
16 totalSum += matrix[i][reverseIndex];
17 }
18 }
19
20 // Return the sum of primary and secondary diagonals, excluding the middle element if counted twice
21 return totalSum;
22 }
23}
24
1#include<vector>
2
3class Solution {
4public:
5 // Function to calculate the sum of the elements on the diagonals of a square matrix
6 int diagonalSum(std::vector<std::vector<int>>& mat) {
7 int total = 0; // Used to store the sum of the diagonal elements
8 int size = mat.size(); // Get the size of the square matrix
9
10 // Iterate through each row of the matrix
11 for (int rowIndex = 0; rowIndex < size; ++rowIndex) {
12 int colIndex = size - rowIndex - 1; // Calculate the column index for the secondary diagonal
13
14 // Sum the primary diagonal element
15 total += mat[rowIndex][rowIndex];
16
17 // Sum the secondary diagonal element only if it's not the same as the primary diagonal element
18 if (rowIndex != colIndex) {
19 total += mat[rowIndex][colIndex];
20 }
21 }
22 return total; // Return the sum of the diagonal elements
23 }
24};
25
1function diagonalSum(matrix: number[][]): number {
2 // 'matrixSize' stores the size of the matrix (number of rows/columns)
3 const matrixSize = matrix.length;
4
5 // Initialize 'sum' to zero, which will store the final diagonal sum
6 let sum = 0;
7
8 // Iterate through each row of the matrix
9 for (let row = 0; row < matrixSize; row++) {
10 // Add the elements from both the primary and secondary diagonals for the current row
11 sum += matrix[row][row] + matrix[row][matrixSize - 1 - row];
12 }
13
14 // If the matrix size is odd, subtract the central element once to correct the sum
15 if (matrixSize % 2 === 1) {
16 // The central element is at the position ['matrixSize' / 2] in both dimensions
17 sum -= matrix[matrixSize >> 1][matrixSize >> 1];
18 }
19
20 // Return the calculated sum of the diagonal elements
21 return sum;
22}
23
Time and Space Complexity
Time Complexity
The provided code traverses each row only once, and within each row, it accesses two elements directly by their index, which is an (O(1)) operation. Since there are n
rows in a square matrix with size (n \times n), the overall time complexity of the code is (O(n)) where (n) is the number of rows (and also the number of columns) in the matrix.
Space Complexity
The code uses a fixed number of variables (ans
, n
, i
, j
, row
). It does not depend on the size of the input matrix, therefore the space complexity is (O(1)), that is, constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.