Matrix Diagonal Sum solution and explanation
Google
9 more videos on this problem
Matrix Diagonal Sum | LeetCode 1572 | C++, Java, PythonKnowledge Center · 6:12 · 23K views
Matrix Diagonal Sum - Leetcode 1572 - PythonNeetCodeIO · 8:55 · 11K views
Matrix Diagonal Sum (LeetCode 1572) | Full solution with visuals | 2 possible scenariosNikhil Lohia · 11:36 · 5K views
Matrix Diagonal Sum Solution | LeetCode 1572codedecks · 10:56 · 5K views
Matrix Diagonal Sum | Leetcode - 1572 | MICROSOFT | Explanation ➕ Live CodingcodestorywithMIK · 19:09 · 4K views
1572 Matrix Diagonal Sum LeetCode (Google Interview Question) JavaScriptdev alex · 5:36 · 4K views
Leetcode | 1572. Matrix Diagonal Sum | Easy | Java SolutionDeveloper Docs · 3:57 · 1K views
Matrix Diagonal Sum | LeetCode 1572 | Explained and Java CodeNate Santti · 10:01 · 1K views
LeetCode 1572 : Matrix Diagonal Sum | Solution in JAVAAmit Manjarly · 5:04 · 624 views
Matrix Diagonal Sum - LeetCode 1572 - Python SolutionCode with Carter · 6:28 · 549 views
The problem
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.
Example 1:
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.
Example 2:
Input: mat = [[1,1,1,1], [1,1,1,1], [1,1,1,1], [1,1,1,1]] Output: 8
Example 3:
Input: mat = [[5]] Output: 5
Constraints:
n == mat.length == mat[i].length1 <= n <= 1001 <= mat[i][j] <= 100
Approach overview
Problem Overview: You are given a square n x n matrix. The task is to compute the sum of its primary diagonal (top-left to bottom-right) and secondary diagonal (top-right to bottom-left). If both diagonals overlap at the center element (when n is odd), that value should only be counted once.
Approach 1: Iterative Diagonal Traversal (O(n) time, O(1) space)
Iterate through the matrix using a single loop from i = 0 to n - 1. For each row index i, the primary diagonal element is mat[i][i] and the secondary diagonal element is mat[i][n - i - 1]. Add both values to a running sum while traversing the matrix once. If the matrix size is odd and the iteration reaches the center (i == n - i - 1), add that element only once to avoid double counting.
This method works because both diagonals can be accessed directly using index relationships. The traversal touches exactly n rows, making the time complexity O(n) and extra space O(1). This is the most straightforward and commonly expected solution when working with arrays and matrix traversal problems.
Approach 2: Pre-calculation for Middle Element (O(n) time, O(1) space)
This approach also iterates once through the matrix and sums both diagonals. The difference is that the algorithm first calculates the total of both diagonals without conditions, then adjusts the result afterward. If the matrix size is odd, the center element mat[n/2][n/2] appears in both diagonals and is counted twice. Subtract that value once from the final sum.
The key idea is separating diagonal accumulation from overlap handling. This keeps the loop simpler because every iteration adds both diagonal elements without checking conditions. After traversal, a single adjustment removes the duplicate middle value when needed. Time complexity remains O(n) with constant O(1) space.
Recommended for interviews: The iterative traversal approach with an inline middle check is usually what interviewers expect. It shows you understand diagonal indexing in a square matrix and can prevent double counting during iteration. The post-adjustment method is equally optimal but slightly less explicit about why the overlap occurs.
Approach 1: Iterative Approach
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]).
def diagonalSum(mat):
n = len(mat)
total_sum = 0
for i in range(n):
total_sum += mat[i][i]
if i != n - i - 1:
total_sum += mat[i][n - i - 1]
return total_sum
# Example usage
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(diagonalSum(matrix))public class DiagonalSum {
public static int diagonalSum(int[][] mat) {
int n = mat.length;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += mat[i][i];
if (i != n - i - 1) {
sum += mat[i][n - i - 1];
}
}
return sum;
}
public static void main(String[] args) {
int[][] mat = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println(diagonalSum(mat));
}
}#include <iostream>
#include <vector>
int diagonalSum(const std::vector<std::vector<int>>& mat) {
int n = mat.size();
int sum = 0;
for (int i = 0; i < n; i++) {
sum += mat[i][i];
if (i != n - i - 1) {
sum += mat[i][n - i - 1];
}
}
return sum;
}
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;
}function diagonalSum(mat) {
let n = mat.length;
let sum = 0;
for (let i = 0; i < n; i++) {
sum += mat[i][i];
if (i !== n - i - 1) {
sum += mat[i][n - i - 1];
}
}
return sum;
}
// Example usage
const mat = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
console.log(diagonalSum(mat));#include <stdio.h>
int diagonalSum(int** mat, int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += mat[i][i];
if (i != n - i - 1) {
sum += mat[i][n - i - 1];
}
}
return sum;
}
int main() {
int* mat[3];
int row1[] = {1, 2, 3};
int row2[] = {4, 5, 6};
int row3[] = {7, 8, 9};
mat[0] = row1;
mat[1] = row2;
mat[2] = row3;
printf("%d\n", diagonalSum(mat, 3));
return 0;
}using System;
class Program {
public static int DiagonalSum(int[][] mat) {
int n = mat.Length;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += mat[i][i];
if (i != n - i - 1) {
sum += mat[i][n - i - 1];
}
}
return sum;
}
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));
}
}This Python function calculates the diagonal sum by iterating through each index of the square matrix and adding the appropriate diagonal elements, taking care to not double-count the middle element in odd-length matrices.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Pre-calculation for Middle Element
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.
def diagonalSum(mat):
n = len(mat)
primary_sum = sum(mat[i][i] for i in range(n))
secondary_sum = sum(mat[i][n - i - 1] for i in range(n))
if n % 2 == 1:
primary_sum -= mat[n // 2][n // 2]
return primary_sum + secondary_sum
# Example usage
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(diagonalSum(matrix))public class DiagonalSum {
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;
}
public static void main(String[] args) {
int[][] mat = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println(diagonalSum(mat));
}
}#include <iostream>
#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;
}function diagonalSum(mat) {
let n = mat.length;
let primarySum = 0, secondarySum = 0;
for (let i = 0; i < n; i++) {
primarySum += mat[i][i];
secondarySum += mat[i][n - i - 1];
}
if (n % 2 === 1) {
primarySum -= mat[Math.floor(n / 2)][Math.floor(n / 2)];
}
return primarySum + secondarySum;
}
// Example usage
const mat = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
console.log(diagonalSum(mat));#include <stdio.h>
int diagonalSum(int** mat, int n) {
int primarySum = 0;
int 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() {
int* mat[3];
int row1[] = {1, 2, 3};
int row2[] = {4, 5, 6};
int row3[] = {7, 8, 9};
mat[0] = row1;
mat[1] = row2;
mat[2] = row3;
printf("%d\n", diagonalSum(mat, 3));
return 0;
}using System;
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));
}
}This Python function efficiently computes the aggregate diagonal sum by separately addressing both the primary and secondary diagonals and then adjusting for any double-counting of a center element.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Row-by-Row Traversal
We can traverse each row row[i] of the matrix. For each row, we calculate the elements on the two diagonals, i.e., row[i][i] and row[i][n - i - 1], where n is the number of rows in the matrix. If i = n - i - 1, it means there is only one element on the diagonals of the current row; otherwise, there are two elements. We add these elements to the answer.
After traversing all rows, we get the answer.
The time complexity is O(n), where n is the number of rows in the matrix. The space complexity is O(1).
function diagonalSum(mat: number[][]): number {
let ans = 0;
const n = mat.length;
for (let i = 0; i < n; ++i) {
const j = n - i - 1;
ans += mat[i][i] + (i === j ? 0 : mat[i][j]);
}
return ans;
}func diagonalSum(mat [][]int) (ans int) {
n := len(mat)
for i, row := range mat {
ans += row[i]
if j := n - i - 1; j != i {
ans += row[j]
}
}
return
}impl Solution {
pub fn diagonal_sum(mat: Vec<Vec<i32>>) -> i32 {
let n = mat.len();
let mut ans = 0;
for i in 0..n {
ans += mat[i][i];
let j = n - i - 1;
if j != i {
ans += mat[i][j];
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n). |
| Pre-calculation for Middle Element | Time Complexity: O(n). |
| Row-by-Row Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Diagonal Traversal | O(n) | O(1) | Best general solution. Directly accesses both diagonals during one pass. |
| Pre-calculation for Middle Element | O(n) | O(1) | Useful when you want a simpler loop and handle the center overlap afterward. |
Frequently asked questions
Is Matrix Diagonal Sum easy or hard?
Matrix Diagonal Sum is classified as an Easy problem on LeetCode with a high acceptance rate around 84%. The challenge mainly involves recognizing diagonal index patterns and correctly handling the center element in odd-sized matrices.
Matrix Diagonal Sum Python/Java solution
Both Python and Java solutions follow the same logic: iterate through indices and sum mat[i][i] and mat[i][n-i-1]. If the matrix size is odd, ensure the center element is counted once. The implementation typically takes fewer than 10 lines in both languages.
How to solve Matrix Diagonal Sum in O(n)?
Iterate from i = 0 to n - 1 and add mat[i][i] (primary diagonal) and mat[i][n - i - 1] (secondary diagonal) to the result. If n is odd and i equals n - i - 1, add the value only once or subtract the center element afterward. This processes both diagonals in a single pass.
What is the best approach for Matrix Diagonal Sum?
The best approach is a single-pass iterative traversal that adds mat[i][i] and mat[i][n-i-1] for each row. This method runs in O(n) time and O(1) space because it only visits each diagonal element once. A small check prevents double counting when the matrix size is odd.
Is Matrix Diagonal Sum asked at Google/Amazon/Meta?
Matrix traversal problems like Matrix Diagonal Sum frequently appear in coding interviews at large tech companies including Amazon and Meta. The question tests understanding of matrix indexing, diagonal patterns, and careful handling of edge cases such as overlapping elements.
What data structure is used in Matrix Diagonal Sum?
The problem uses a 2D array (matrix). The algorithm relies on index relationships within the matrix to directly access diagonal elements rather than storing additional structures.
What is the time complexity of Matrix Diagonal Sum?
The optimal solution runs in O(n) time where n is the dimension of the square matrix. Only one iteration over the rows is required to access both diagonals. Space complexity remains O(1) since no additional data structures are used.