Teaching Kids Programming – Square Matrix Diagonal Sum


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: 5

Hints:
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) —

GD Star Rating
loading...
341 words
Last Post: BASH Function to Error Warnings and Messages with Terminal Colours
Next Post: Check if All Characters Have Equal Number of Occurrences

The Permanent URL is: Teaching Kids Programming – Square Matrix Diagonal Sum

Leave a Reply