498.-diagonal-traverse.md

498. Diagonal Traverse

{% tabs %} {% tab title="Python" %}

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        
        ## it a BFS level
        if not matrix :return []
        
        n = len(matrix)
        m = len(matrix[0])
        
        i = j = 0
        dit = collections.defaultdict(list)
        ans = []
        for i in range(n):
            for j in range(m):
                dit[i + j].append(matrix[i][j])
        for i in range(len(dit)):
            if i % 2 != 1:
                ans += dit[i][::-1]
            else:
                ans += dit[i]
            
        return ans 
            
            

{% endtab %}

{% tab title="Python - TLE" %}

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        
        ## it a BFS level
        if not matrix :return []
        
        n = len(matrix)
        m = len(matrix[0])
        
        i = j = 0
        q = collections.deque()
        q.append((i,j))
        level = 0
        ans = []
        while level < m + n - 1 :
            tmp = []
            for i in range(level + 1):
                if 0 <= level - i < n and 0 <= i < m:
                    tmp.append(matrix[level - i][i])
            if level % 2 == 1:
                ans += tmp[::-1]
                
            else:
                ans += tmp
            level += 1
            
        return ans 
            
            

{% endtab %} {% endtabs %}