Teaching Kids Programming: Videos on Data Structures and Algorithms
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:
1 2 3 Input: mat = [[1,2,3], [4,5,6], [7,8,9]]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:
1 2 3 4 Input: mat = [[1,1,1,1], [1,1,1,1], [1,1,1,1], [1,1,1,1]]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: 5Hints:
There will be overlap of elements in the primary and secondary diagonals if and only if the length of the matrix is odd, which is at the center.
Compute the Diagonals Sums of a Square Matrix
The tricky part is to avoid computing the central if the dimension is even. We iterate i from 0 to n-1 and sum up the diagonals values at [i][i] and [i][n-i-1].
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: def diagonalSum(self, mat: List[List[int]]) -> int: n = len(mat) if n == 1: return mat[0][0] ans = 0 for i in range(n): ans += mat[i][i] j = n - i - 1 if j != i: ans += mat[i][j] return ans |
class Solution: def diagonalSum(self, mat: List[List[int]]) -> int: n = len(mat) if n == 1: return mat[0][0] ans = 0 for i in range(n): ans += mat[i][i] j = n - i - 1 if j != i: ans += mat[i][j] return ans
Time complexity is O(N). See also: Compute the Number Spiral Diagonals
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: BASH Function to Error Warnings and Messages with Terminal Colours
Next Post: Check if All Characters Have Equal Number of Occurrences