498. Diagonal Traverse

Problem Statement

link: LeetCode.cn LeetCode Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,4,7,5,3,6,8,9]

Input: mat = [[1,2],[3,4]] Output: [1,2,3,4]

Solution Approach

The algorithm traverses the matrix diagonally, alternating directions, and appending elements to the result array.

Algorithm

1. Initialize a loop iterating over the sum of the number of rows and columns minus one.
2. Within the loop, for even iterations, traverse upwards diagonally from the current position, appending elements to the result.
3. For odd iterations, traverse downwards diagonally from the current position, appending elements to the result.

Implement

    class Solution:
  def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
      m, n = len(mat), len(mat[0])
      res = []
      for i in range(m + n - 1):
          if i % 2 == 0:
              for x in range(min(i, m - 1), max(0, i - n + 1) - 1, -1):
                  res.append(mat[x][i - x])
          else:
              for x in range(max(0, i - n + 1), min(i, m - 1) + 1):
                  res.append(mat[x][i - x])
      return res

    
    

Twitter  facebook  Email