Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Cells on the same upward-right diagonal share the same sum of row and column indices. Grouping them first separates two concerns: identifying each diagonal and choosing its traversal direction. Row-major collection orders each bucket from top-right toward bottom-left, so reversing alternating buckets produces the zigzag.

Approach

Scan the matrix row by row and append each cell to its diagonal bucket. Python uses columns - 1 - column - row, an equivalent key that is constant for each diagonal.
Process diagonals in the order they first appear, starting with the top-left cell's diagonal.
Reverse the first bucket, keep the second as collected, and continue alternating. Append each bucket's values to the result.
Return the concatenation. Single-row and single-column matrices work without special cases because their buckets contain one element each.

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        n = len(mat)
        m = len(mat[0])
        d = defaultdict(list)

        for i in range(n):
            for j in range(m):
                d[m - 1 - j - i].append(mat[i][j])

        res = []
        curr = 1

        for k in d:
            if curr:
                res += d[k][::-1]
            else:
                res += d[k]
            curr ^= 1

        return res

Complexity analysis

For an R × C matrix, both displayed implementations take O(RC) time and use O(RC) auxiliary space for all diagonal buckets, excluding the O(RC) returned output.