LeetCode #498 Diagonal Traverse

Medium

Problem

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

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

Note:

1. The total number of elements of the given matrix will not exceed 10,000.

Solution

We are going to go up-right or down-left position, but there are four edge cases need to be considered:

1. On top bolder in up trend: go right
2. On right bolder in up trend: go down
3. On left bolder in down trend: go down
4. On bottom bolder in down trend: go right

It’s noted that case 2 will take precedence of case 1 if you are on top-right corner exactly. And case 4 will take precedence of case 3 on bottom-left corner.

Complexity

Iterating each element in matrix takes O(mn) time which m denotes to row count and n to column count.

There is also a list with O(mn) space for returning result.