Matrix Diagonal Sum — сумма элементов на двух диагоналях квадратной матрицы

Условие

Дана квадратная матрица mat[n][n]. Найдите сумму элементов на главной и побочной диагоналях. Если центральный элемент попадает на обе диагонали (при нечётном n), его учитывать только один раз.

Пример.

[[1,2,3],
 [4,5,6],
 [7,8,9]]
Главная: 1+5+9 = 15
Побочная: 3+5+7 = 15
Сумма: 25 (5 учли один раз)

Решение

Идём по строкам i от 0 до n-1. На главной диагонали — элемент mat[i][i], на побочной — mat[i][n-1-i]. Если i == n-1-i (центр при нечётном n), это один и тот же элемент — добавляем один раз.

Код (Python)

class Solution:
    def diagonalSum(self, mat: list[list[int]]) -> int:
        n = len(mat)
        total = 0
        for i in range(n):
            total += mat[i][i]
            if i != n - 1 - i:
                total += mat[i][n - 1 - i]
        return total

Сложность

• Время: O(n) — мы проходим только по диагональным элементам, а не по всей матрице.
• Память: O(1).

Подводные камни

1. Двойной учёт центра. При n = 3 центральный элемент mat[1][1] лежит на обеих диагоналях. Без проверки i != n - 1 - i его засчитают дважды.
2. O(n^2) через двойной цикл. Не нужно — диагональных элементов ровно 2n - 1.
3. Прямоугольная матрица. Условие гарантирует квадрат; для общего случая (m × n) нужно отдельно решать (главная — min(m, n) штук).

Эталонный ответ

Один проход по i, сумма mat[i][i] + mat[i][n-1-i] с защитой от двойного учёта центра. O(n).