Diagonal Traverse

Medium~20 min

Given an m x n matrix of integers, return all elements ordered by diagonal.

Diagonals are defined by the sum row + col. Elements with the same row + col value belong to the same diagonal. Start from diagonal 0 (top-left corner) and proceed to the last diagonal.

Within each diagonal, elements are ordered from top to bottom (i.e., by increasing row index).

For example, in a 3x3 matrix:

Diagonal 0: (0,0)
Diagonal 1: (0,1), (1,0)
Diagonal 2: (0,2), (1,1), (2,0)
Diagonal 3: (1,2), (2,1)
Diagonal 4: (2,2)

Examples

Example 1

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

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

Explanation: Diagonal 0: [1]. Diagonal 1: [2, 4]. Diagonal 2: [3, 5, 7]. Diagonal 3: [6, 8]. Diagonal 4: [9].

Example 2

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

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

Explanation: Diagonal 0: [1]. Diagonal 1: [2, 3]. Diagonal 2: [4, 5]. Diagonal 3: [6].

Constraints

1 <= m, n <= 100
-10^4 <= matrix[i][j] <= 10^4
The matrix is non-empty

Code

Ctrl+EnterRun|Ctrl+⇧+EnterSubmit

Output

Run your code to see results

Use Cmd+Enter to run