Skip to content

498. Diagonal Traverse

Array Matrix Simulation

Problem - Diagonal Traverse

Medium

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

 

Example 1:

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

Example 2:

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

 

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • -105 <= mat[i][j] <= 105

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        result = []

        for k in range (m + n - 1):
            tmp = []
            i = 0 if k < n else k - n +1
            j = k if k < n else n - 1

            while i < m and j >= 0:
                tmp.append(mat[i][j])
                i += 1
                j -= 1

            if k % 2 == 0:
                tmp = tmp[::-1]
            result.extend(tmp)

        return result

Submission Stats:

  • Runtime: 7 ms (81.53%)
  • Memory: 19.8 MB (55.25%)