LC 0498 [M] Diagonal Traverse - ALawliet/algorithms GitHub Wiki

use r+c as the key for a list of diagonal elements, then reverse the even r+c lists

class Solution(object):
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        ROWS = len(matrix)
        COLS = len(matrix[0])

        rc_to_diaglist = defaultdict(list)
        for r in range(ROWS):
            for c in range(COLS):
                rc_to_diaglist[r+c].append(matrix[r][c])

        ans = []
        for rc, diaglist in rc_to_diaglist.items():
            if rc % 2 == 0: # even
                ans += reversed(diaglist)
            else: # odd
                ans += diaglist 
        return ans

class Solution(object):
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        n_rows = len(matrix)
        n_cols = len(matrix[0])
        d = defaultdict(list)
		#loop through matrix
        for r in range(n_rows):
            for c in range(n_cols):
				#if no entry in dictionary for sum of indices aka the diagonal, create one
				#If you've already passed over this diagonal, keep adding elements to it!
                d[r+c].append(matrix[r][c])
		# 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