There's a noticeable pattern in this traversal:
- M+N-1 total traversals
- since it alternates up and down, we can use modulo to figure out the direction we're on
- 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)-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