diagonal_traverse
1from collections import defaultdict 2 3 4# @leet start 5class Solution: 6 def findDiagonalOrder(self, mat: list[list[int]]) -> list[int]: 7 """ 8 This question asks us to return the diagonal traverse of a matrix, 9 where for [[1,2,3], [4,5,6], [7,8,9]], the traverse goes up, then down, 10 and reverses. 11 12 Thus, we want to return a flattened traversal. 13 14 To do so, note that the rows for the correct traversal look like this: 15 16 (0, 0) 17 (1, 0), (0, 1) 18 (2, 0), (1, 1), (0, 2) 19 (2, 1), (1, 2) 20 (2, 2) 21 22 Thus, we want to group rows based on the sum of their y and x coordinates. 23 Also, since the traversal reverses from up and down, we know that we can 24 reverse each level based on its parity (if the level is even or odd). 25 We can just reverse each even numbered row with this traversal to get 26 the correct answer. 27 """ 28 m, n = len(mat), len(mat[0]) 29 rows = defaultdict(list) 30 31 for y in range(m): 32 for x in range(n): 33 rows[y + x].append(mat[y][x]) 34 35 res = [] 36 for k, v in rows.items(): 37 if k % 2 == 0: 38 v.reverse() 39 res.extend(v) 40 41 return res 42 43 44# @leet end 45 46 47def test(): 48 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def findDiagonalOrder(self, mat: list[list[int]]) -> list[int]: 8 """ 9 This question asks us to return the diagonal traverse of a matrix, 10 where for [[1,2,3], [4,5,6], [7,8,9]], the traverse goes up, then down, 11 and reverses. 12 13 Thus, we want to return a flattened traversal. 14 15 To do so, note that the rows for the correct traversal look like this: 16 17 (0, 0) 18 (1, 0), (0, 1) 19 (2, 0), (1, 1), (0, 2) 20 (2, 1), (1, 2) 21 (2, 2) 22 23 Thus, we want to group rows based on the sum of their y and x coordinates. 24 Also, since the traversal reverses from up and down, we know that we can 25 reverse each level based on its parity (if the level is even or odd). 26 We can just reverse each even numbered row with this traversal to get 27 the correct answer. 28 """ 29 m, n = len(mat), len(mat[0]) 30 rows = defaultdict(list) 31 32 for y in range(m): 33 for x in range(n): 34 rows[y + x].append(mat[y][x]) 35 36 res = [] 37 for k, v in rows.items(): 38 if k % 2 == 0: 39 v.reverse() 40 res.extend(v) 41 42 return res
def
findDiagonalOrder(self, mat: list[list[int]]) -> list[int]:
7 def findDiagonalOrder(self, mat: list[list[int]]) -> list[int]: 8 """ 9 This question asks us to return the diagonal traverse of a matrix, 10 where for [[1,2,3], [4,5,6], [7,8,9]], the traverse goes up, then down, 11 and reverses. 12 13 Thus, we want to return a flattened traversal. 14 15 To do so, note that the rows for the correct traversal look like this: 16 17 (0, 0) 18 (1, 0), (0, 1) 19 (2, 0), (1, 1), (0, 2) 20 (2, 1), (1, 2) 21 (2, 2) 22 23 Thus, we want to group rows based on the sum of their y and x coordinates. 24 Also, since the traversal reverses from up and down, we know that we can 25 reverse each level based on its parity (if the level is even or odd). 26 We can just reverse each even numbered row with this traversal to get 27 the correct answer. 28 """ 29 m, n = len(mat), len(mat[0]) 30 rows = defaultdict(list) 31 32 for y in range(m): 33 for x in range(n): 34 rows[y + x].append(mat[y][x]) 35 36 res = [] 37 for k, v in rows.items(): 38 if k % 2 == 0: 39 v.reverse() 40 res.extend(v) 41 42 return res
This question asks us to return the diagonal traverse of a matrix, where for [[1,2,3], [4,5,6], [7,8,9]], the traverse goes up, then down, and reverses.
Thus, we want to return a flattened traversal.
To do so, note that the rows for the correct traversal look like this:
(0, 0) (1, 0), (0, 1) (2, 0), (1, 1), (0, 2) (2, 1), (1, 2) (2, 2)
Thus, we want to group rows based on the sum of their y and x coordinates. Also, since the traversal reverses from up and down, we know that we can reverse each level based on its parity (if the level is even or odd). We can just reverse each even numbered row with this traversal to get the correct answer.
def
test():