python O(MN) O(1) space (excluding return arr)


  • 0

    There's a noticeable pattern in this traversal:

    1. M+N-1 total traversals
    2. since it alternates up and down, we can use modulo to figure out the direction we're on
    3. we just need to figure out which index the current diagonal traversal starts on. This can be obtained by
      using which iteration we're currently on.

    If anyone wants a more detailed explanation, I'd be happy to walk them through the logic.

        def findDiagonalOrder(self, matrix):
    
            if not matrix: return []
            res = []
            m, n = len(matrix[0])-1, len(matrix)-1
            r, c, rM, cM = 0, 0, -1, 1
            for i in range(m+n+2): # +2 to offset 0 indexing
                if i % 2 == 0: r, c = min(i, n), max(0, i-n)
                else: r, c = max(0, i-m), min(i, m)
                while n >= r >= 0 and m >= c >= 0: # traversal
                    res.append(matrix[r][c])
                    r, c = r + rM, c + cM
                rM, cM = rM * -1, cM * -1 # flip direction
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.