Diagonal Traverse

Medium · matrix

You are given an m x n grid of integers called matrix. Return all of its values in a single list, reading the grid one diagonal at a time in a zig-zag.

Cells on the same diagonal are the ones where row + col has the same value. Start with the diagonal row + col = 0, which is just the top-left cell, then 1, 2, and so on until the bottom-right cell. The direction alternates:

when row + col is odd, read the diagonal from its top-right end down to its bottom-left end;
when row + col is even, read it from its bottom-left end up to its top-right end.

For example, the grid below is read as 1, 2, 4, 7, 5, 3, 6, 8, 9.

1 2 3
4 5 6
7 8 9

Examples

Example 1

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Output: [1, 2, 4, 7, 5, 3, 6, 8, 9]

Diagonal 1 is read 2 then 4, diagonal 2 is read 7, 5, 3, diagonal 3 is read 6 then 8, and diagonal 4 is just 9.

Example 2

Input: matrix = [[1, 2], [3, 4], [5, 6]]

Output: [1, 2, 3, 5, 4, 6]

A grid with more rows than columns: diagonal 1 gives 2, 3, diagonal 2 gives 5, 4, and diagonal 3 is just 6.

Example 3

Input: matrix = [[7, 8, 9]]

Output: [7, 8, 9]

With a single row every diagonal is one cell, so the order is simply left to right.

Constraints

1 <= m, n <= 300
matrix[i].length == n for every row
-10^5 <= matrix[i][j] <= 10^5