-
Notifications
You must be signed in to change notification settings - Fork 0
/
diagonal_traverse.py
35 lines (34 loc) · 1.17 KB
/
diagonal_traverse.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution(object):
def findDiagonalOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
d={}
#loop through matrix
for i in range(len(matrix)):
for j in range(len(matrix[i])):
#if no entry in dictionary for sum of indices aka the diagonal, create one
if i + j not in d:
d[i+j] = [matrix[i][j]]
else:
#If you've already passed over this diagonal, keep adding elements to it!
d[i+j].append(matrix[i][j])
# we're done with the pass, let's build our answer array
ans= []
#look at the diagonal and each diagonal's elements
for entry in d.items():
#each entry looks like (diagonal level (sum of indices), [elem1, elem2, elem3, ...])
#snake time, look at the diagonal level
if entry[0] % 2 == 0:
#Here we append in reverse order because its an even numbered level/diagonal.
[ans.append(x) for x in entry[1][::-1]]
else:
[ans.append(x) for x in entry[1]]
return ans
abc = Solution()
abc.findDiagonalOrder(
[[1,2,3],
[4,5,6],
[7,8,9]]
)