Show problems as
Classic problem #1424MediumArraySortingHeap (Priority Queue)

Diagonal Traverse II

Real-world version: Ragged Hall Call Order
Tracked in this browser only
Read Diagonal Traverse II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A lecture hall is described by seats, a list of rows. Row r holds seats[r].length seats and seats[r][c] is the badge number of the seat in position c of that row, counting from 0. Rows may hold very different numbers of seats, so seats is ragged: nothing guarantees that two rows are the same length.

An usher calls the badges in groups. The group of a seat is r + c, its row index plus its position in the row. Groups are called in increasing order of that number, and inside one group the seats are called from the largest row index down to the smallest.

Return the badge numbers in the order they are called.

Examples

Example 1

Input
seats = [[1, 2, 3, 4, 5, 6, 7, 8], [9], [10, 11], [12, 13, 14, 15]]
Output
[1, 9, 2, 10, 3, 12, 11, 4, 13, 5, 14, 6, 15, 7, 8]

Group 0 holds only badge 1. Group 1 holds badge 2 from row 0 and badge 9 from row 1, and the higher row is called first, so badge 9 comes before badge 2. Group 2 holds badge 3 from row 0, badge 10 from row 2 and nothing from row 1, since row 1 has no seat in position 1, so the order there is 10 then 3. The remaining groups follow the same rule.

Example 2

Input
seats = [[9, 8, 7]]
Output
[9, 8, 7]

With a single row, the group numbers are 0, 1 and 2, one seat each, so the badges come out in row order.

Example 3

Input
seats = [[4], [5], [6]]
Output
[4, 5, 6]

Every row holds one seat, so again each group holds a single badge: group 0 is badge 4, group 1 is badge 5 and group 2 is badge 6.

Constraints

  • 1 <= seats.length <= 10^5
  • 1 <= seats[i].length <= 10^5
  • 1 <= seats[i][j] <= 10^5
  • The hall holds at most 10^5 seats in total.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def diagonal_call_order(seats: list[list[int]]) -> list[int]:
Java
public int[] diagonalCallOrder(List<List<Integer>> seats)

More on the same topics