1572. Matrix Diagonal Sum

1572. Matrix Diagonal Sum

Tag: Depth-First Search Breadth-First Search Matrix

Difficulty: Easy

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].length
• 1 <= n <= 100
• 1 <= mat[i][j] <= 100

---

Depth-First Search

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        ROWS, COLS = len(mat), len(mat[0])
        visited = set()
        ans = 0

        def dfs(row, col, is_right):
            nonlocal ans
            # Base cases
            if not (0 <= row < ROWS and 0 <= col < COLS):
                return
            if (row, col) in visited:
                ans -= mat[row][col]

            ans += mat[row][col]
            visited.add((row, col))
            if is_right:
                dfs(row + 1, col + 1, is_right)
            else:
                dfs(row + 1, col - 1, is_right)

            return ans
        
        dfs(0, 0, True)
        dfs(0, COLS - 1, False)
        return ans

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        ROWS, COLS = len(mat), len(mat[0])
        rightward, leftward = [(1, 1)], [(1, -1)]
        visited = set()
        ans = 0

        def dfs(row, col, is_right):
            nonlocal ans
            # Base cases
            if not (0 <= row < ROWS and 0 <= col < COLS):
                return 0
            if (row, col) in visited:
                ans -= mat[row][col]

            ans += mat[row][col]
            visited.add((row, col))
            if is_right:
                direction = rightward
            else:
                direction = leftward

            [dfs(row + dx, col + dy, is_right) for dx, dy in direction]
            return ans
        
        dfs(0, 0, True)
        dfs(0, COLS - 1, False)
        return ans

---

Breadth-First Search

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        ROWS, COLS = len(mat), len(mat[0])
        rightward, leftward = [(1, 1)], [(1, -1)]
        visited = set()
        ans = 0

        queue = collections.deque([(0, 0, True), (0, COLS - 1, False)])

        while queue:
            row, col, is_right = queue.popleft()
            if not (0 <= row < ROWS and 0 <= col < COLS):
                continue
            if (row, col) in visited:
                ans -= mat[row][col]

            ans += mat[row][col]
            visited.add((row, col))
            if is_right:
                direction = rightward
            else:
                direction = leftward

            for next_row, next_col in [(row + dx, col + dy) for dx, dy in direction]:
                queue.append((next_row, next_col, is_right))

        return ans

---

Matrix

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        n = len(mat)
        ans = 0

        for i in range(n):
            ans += mat[i][i]
            ans += mat[n - 1 - i][i]

        if n % 2 != 0:
            ans -= mat[n // 2][n // 2]

        return ans

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        n = len(mat)
        ans = 0

        for i in range(n):
            ans += mat[i][i]
            if i == n - 1 - i:
                continue
            ans += mat[n - 1 - i][i]

        return ans

One Liner

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

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        return sum(row[i] + row[len(mat) - i - 1] for i, row in enumerate(mat)) - mat[len(mat) // 2][len(mat) // 2] * (len(mat) % 2)