Matrix Diagonal Sum
Problem Description
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.
What is a Square Matrix?
A square matrix is a grid of numbers with an equal number of rows and columns. For example:
Matrix: 1 2 3
4 5 6
7 8 9
This is a 3x3 matrix because it has 3 rows and 3 columns.
Square matrices are special because they have two important diagonals:
- Primary Diagonal: This diagonal goes from the top-left corner to the bottom-right corner (elements 1, 5, 9 in the above example).
- Secondary Diagonal: This diagonal goes from the top-right corner to the bottom-left corner (elements 3, 5, 7 in the above example).
Example
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.
Input: mat = [[1,1,1,1],
[1,1,1,1],
[1,1,1,1],
[1,1,1,1]]
Output: 8
Constraints
- n == mat.length == mat[i].length
- 1 <= n <= 100
- 1 <= mat[i][j] <= 100
The initial idea is to simply traverse the given matrix and sum the elements at the diagonal indices. The main focus, therefore, is to determine how to identify these indices effectively. Let’s explore how we can approach this.
Optimal Approach
Intuition
The problem asks us to calculate the sum of all diagonal elements in a square matrix. Let’s break this into two clear tasks:
- Add all elements in the primary diagonal:
The primary diagonal starts from the top-left corner of the matrix and goes down to the bottom-right corner. For example, in a 3x3 matrix, the elements on the primary diagonal are the ones where the row and column indices are the same (mat[0][0], mat[1][1], mat[2][2]). So, our first task is to identify and sum these elements. - Add all elements in the secondary diagonal:
The secondary diagonal starts from the top-right corner and goes down to the bottom-left corner. In a 3x3 matrix, these elements are at positions where the sum of the row and column indices equals the size of the matrix minus one (mat[0][2], mat[1][1], mat[2][0]). We need to add these elements to the total.
However, there’s one special case we need to handle:
- Avoid double-counting the middle element:
If the matrix size is odd (like a 3x3 matrix), the center element (e.g., mat[1][1]) belongs to both the primary and secondary diagonals. Since it gets added when we calculate the primary diagonal, we should not add it again when calculating the secondary diagonal.
How to Identify Diagonal Elements?
The tricky part here is identifying which elements belong to the diagonals. Let’s break it down:
- Primary Diagonal:
In the primary diagonal, the row index is equal to the column index. For example:
- In mat[0][0], row = 0 and column = 0 → It's a primary diagonal element.
- In mat[1][1], row = 1 and column = 1 → It's a primary diagonal element.
- In general, any element mat[i][i] belongs to the primary diagonal.
- Secondary Diagonal:
In the secondary diagonal, the row index + column index = size of the matrix - 1. For example:
- In mat[0][2], row = 0, column = 2 → 0 + 2 = 2, which equals size - 1 for a 3x3 matrix.
- In mat[1][1], row = 1, column = 1 → 1 + 1 = 2, which equals size - 1.
- In general, any element mat[i][n - 1 - i] (where n is the size of the matrix) belongs to the secondary diagonal.
How to Handle Overlapping Elements?
When the matrix size is odd, there’s a unique situation where the center element of the matrix belongs to both the primary and secondary diagonals. For example, in a 3x3 matrix:
Matrix : 1 2 3
4 5 6
7 8 9
The center element, mat[1][1], lies on both diagonals:
- It is part of the primary diagonal (top-left to bottom-right).
- It is also part of the secondary diagonal (top-right to bottom-left).
If we simply sum both diagonals without any care, this center element will be counted twice. To avoid this, we need to skip adding it again when summing the secondary diagonal.
How can we identify the center element?
- The center element appears when the row index i is equal to the column index i (primary diagonal) and the row index i is equal to n - 1 - i (secondary diagonal).
- This happens only when i == n - 1 - i.
So, for such cases (only in odd-sized matrices), we skip adding the element from the secondary diagonal to avoid double-counting. This ensures the total sum is accurate.
Approach
Step 1 : Initialize Variables
- A variable totalSum to keep track of the total sum, initialized to 0.
- The size of the matrix as n.
Step 2: Traverse the Matrix
- To find the diagonal elements, we’ll loop through the rows of the matrix, and For every row i, compute:
- The primary diagonal element as mat[i][i].
- The secondary diagonal element as mat[i][n - 1 - i].
- Add these elements to totalSum. However, handle the special case of overlapping elements for odd-sized matrices:
- If the current row index i corresponds to the middle row (i.e., i == n - 1 - i), skip adding the secondary diagonal element again.
Step 3: Return the Total Sum
- After the loop finishes, totalSum will hold the sum of all diagonal elements, considering the overlap. Return this value.
Dry Run
Input:
mat = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Initialization:
- n = 3
- totalSum = 0
Loop Iterations:
- Iteration 1 (i = 0):
- Primary diagonal: mat[0][0] = 1
- Secondary diagonal: mat[0][2] = 3
- totalSum = 1 + 3 = 4
- Iteration 2 (i = 1):
- Primary diagonal: mat[1][1] = 5
- Secondary diagonal: mat[1][1] = 5 (skip because i == n - 1 - i)
- totalSum = 4 + 5 = 9
- Iteration 3 (i = 2):
- Primary diagonal: mat[2][2] = 9
- Secondary diagonal: mat[2][0] = 7
- totalSum = 9 + 9 + 7 = 25
Final Output: totalSum = 25
Code for All Languages
C++
class Solution {
public:
// Function to calculate the sum of the diagonals
int diagonalSum(vector<vector<int>>& mat) {
// Get the size of the matrix
int n = mat.size();
// Variable to store the total sum of diagonals
int totalSum = 0;
// Loop through each row of the matrix
for (int i = 0; i < n; i++) {
// Add the primary diagonal element (row = column)
totalSum += mat[i][i];
// Add the secondary diagonal element (row + column = n - 1)
// but avoid adding the center element twice in odd-sized matrices
if (i != n - 1 - i) {
totalSum += mat[i][n - 1 - i];
}
}
// Return the final sum of both diagonals
return totalSum;
}
};Java
class Solution {
// Method to calculate the sum of the diagonals of a matrix
public int diagonalSum(int[][] mat) {
// Get the size of the matrix
int n = mat.length;
// Variable to store the total sum of both diagonals
int totalSum = 0;
// Loop through each row of the matrix
for (int i = 0; i < n; i++) {
// Add the primary diagonal element (row == column)
totalSum += mat[i][i];
// Add the secondary diagonal element (row + column == n - 1)
// but avoid adding the center element twice in odd-sized matrices
if (i != n - 1 - i) {
totalSum += mat[i][n - 1 - i];
}
}
// Return the final sum of both diagonals
return totalSum;
}
}Python
class Solution:
# Method to calculate the sum of the diagonals of a matrix
def diagonalSum(self, mat: List[List[int]]) -> int:
# Get the size of the matrix
n = len(mat)
# Variable to store the total sum of both diagonals
totalSum = 0
# Loop through each row of the matrix
for i in range(n):
# Add the primary diagonal element (row == column)
totalSum += mat[i][i]
# Add the secondary diagonal element (row + column == n - 1)
# but avoid adding the center element twice in odd-sized matrices
if i != n - 1 - i:
totalSum += mat[i][n - 1 - i]
# Return the final sum of both diagonals
return totalSum
Javascript
// Function to calculate the sum of the diagonals of a matrix
var diagonalSum = function(mat) {
// Get the size of the matrix
let n = mat.length;
// Variable to store the total sum of both diagonals
let totalSum = 0;
// Loop through each row of the matrix
for (let i = 0; i < n; i++) {
// Add the primary diagonal element (row == column)
totalSum += mat[i][i];
// Add the secondary diagonal element (row + column == n - 1)
// but avoid adding the center element twice in odd-sized matrices
if (i !== n - 1 - i) {
totalSum += mat[i][n - 1 - i];
}
}
// Return the final sum of both diagonals
return totalSum;
};
Time Complexity : O(n)
Loop Execution:
- We loop over each row of the matrix, which runs n times (where n is the size of the matrix).
- In each iteration, we access two elements (primary and secondary diagonal), and perform simple additions. This is done in constant time O(1).
- Thus, the loop runs in O(n) time.
Final Time Complexity:
- The overall time complexity is O(n).
Space Complexity : O(1)
Auxiliary Space Complexity: O(1)
- The auxiliary space refers to the extra space used by the algorithm aside from the input.
- In this case, we are using only a few variables: n (size of the matrix) and totalSum (the sum of diagonal elements). These variables require constant space, O(1).
Total Space Complexity: O(n^2)
- The total space includes both the input (the matrix) and the auxiliary space.
- The input matrix mat takes O(n^2) space, as it is an n x n matrix.
- The algorithm does not use any additional space proportional to the size of the input, except for the few constant variables.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a 0-indexed two-dimensional integer array nums, return the largest prime number found on at least one of its diagonals. If no prime number is present on the diagonals, return 0. A prime number is greater than 1 and has no divisors other than 1 and itself.
Given an m x n matrix mat of integers, sort each diagonal of the matrix in ascending order and return the modified matrix. A diagonal is defined as a line of cells starting from any element in the topmost row or leftmost column, extending diagonally down to the right.