Diagonal Traverse

medium

Given an m x n matrix, return all elements of the matrix in diagonal order as described below:

Start from the element at the top left corner, move to the next diagonal that moves upward and right (top-right direction). When this diagonal reaches the right or top boundary, change the direction toward bottom-left and so on alternately. If you reach the bottom or the left boundary, switch to top-right direction again and continue until all elements have been visited.

Example 1

Input

Output

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

Explanation. Starting from top-left, move upward and right to cover [1, 2]; move downward and left to cover [4, 7], and so forth alternatingly until all elements are covered.

Example 2

Input

Output

[1, 2, 3, 4]

Explanation. Move from top-left to top-right and then bottom-left to bottom-right diagonally.

Example 3

Input

[
  [
    1
  ]
]

Output

[1]

Explanation. There is only one element, so it's the only element in the diagonal traversal.

Follow-up: How would you adjust your solution if you were required to return elements in a reverse diagonal order?

Constraints:

1. The number of rows `m` and columns `n` in the matrix is at least 1. 2. All entries in the matrix are integers.