Ragged Rows by Diagonal

Medium

You get a list of rows rows, and the rows may have different lengths. The element rows[i][j] sits on diagonal number i + j. List all elements, going through the diagonals in increasing order. Within one diagonal go from bottom to top: the element with the larger row index i comes first. If a row is too short to have a cell on that diagonal, just skip it. Return the resulting list.

Example 1

rows=[[4, 7, 1], [9], [2, 6]] → [4, 9, 7, 2, 1, 6]

Diagonal 0: 4. Diagonal 1, bottom to top: 9, 7. Diagonal 2: 2 (row 2), row 1 has no such cell, then 1. Diagonal 3: just 6.

Example 2

rows=[[3], [5, 8, 11]] → [3, 5, 8, 11]

3, then 5, then 8 and 11, each alone on its diagonal.

Example 3

rows=[[12, 13, 14]] → [12, 13, 14]

Constraints

1 ≤ len(rows) ≤ 10⁵
1 ≤ len(rows[i])
the total length of all rows ≤ 10⁵
1 ≤ rows[i][j] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Sorting Heap (Priority Queue)

Similar problems

K-th Highest Score Medium Studios for Recording Sessions Medium Most Common Values Medium K-th Smallest in a Sorted Grid Medium Jobs With a Cooldown Medium

Input

rows=[[4, 7, 1], [9], [2, 6]]

Expected

[4, 9, 7, 2, 1, 6]

Run checks the first 3 tests in your browser. Submit checks all 73 tests on the server, hidden ones included.