1424. Diagonal Traverse II

solution 1.a: traverse the diagonal based on rule

this solution is expensive as it is like traversing a sparse matrix where not every cell contains value. Time complexity is O(m * n) where m is length of nums and n is the length of longest list in nums

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        m = len(nums)
        n = 0
        for i in range(m):
            n = max(n, len(nums[i]))

        # 0, 0
        # 1,0 0,1
        # 2,0 1,1 0,2
        # 3,0 2,1 1,2 0,3 

        res = []
        for row in range(m-1):
            for col in range(row+1):
                if col < len(nums[row-col]):
                    res.append(nums[row-col][col])

        # 4,0 3,1 2,2 1,3 0,4
        # 4,1 3,2 2,3 1,4 0,5
        for col in range(n):
            for row in range(m-1, -1, -1):
                # c + row = col+m-1
                c = m-1+col-row
                if 0 <= c < len(nums[row]):
                    res.append(nums[row][c])
        
        return res

solution 1.b: an improved version of 1.a is t oiterate every element and group them based on rules that row+col are equal on the same diagonal

To move towards up-right direction, row decreases and col increases.
To avoid checking empty cell, it uses for col in range(len(nums[row]))

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        groups = collections.defaultdict(list)
        for row in range(len(nums)-1, -1, -1): # row decreases in up-right direction
            for col in range(len(nums[row])): # col increases in up-right direction
                diagonal = row + col
                groups[diagonal].append(nums[row][col])
        
        res = []
        diagonal = 0
        while diagonal in groups:
            res.extend(groups[diagonal])
            diagonal += 1
        return res

solution 2: bfs

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        if not nums or not nums[0]:
            return []
        
        row = len(nums)
        queue = collections.deque([(0, 0)])
        res = []
        while queue:
            r, c = queue.popleft()
            res.append(nums[r][c])

            if c == 0 and r + 1 < row: # always go downwards first as it starts from bottom left
                queue.append((r+1, c))
            if c + 1 < len(nums[r]): # note each row has different lengths 
                queue.append((r, c+1))
            
        return res

1424. Diagonal Traverse II - cocoder39/coco39_LC GitHub Wiki