Show problems as
Classic problem #406MediumArrayBinary Indexed TreeSegment TreeSorting

Queue Reconstruction by Height

Real-world version: Rebuild the Photo Line
Tracked in this browser only
Read Queue Reconstruction by Height on LeetCode(opens in a new tab)

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

A guide lined a walking group up single file for a photo, wrote one record per hiker, then shuffled the records.

hikers[i] = [height, ahead] is one such record: that hiker measures height centimetres, and of the hikers who stood in front of them in the line, exactly ahead measured height centimetres or more. Hikers of the same height therefore count each other.

Rebuild the line. Return a list ordered from the front of the line to the back, where entry j is the [height, ahead] record of the hiker who stood in position j. Exactly one line agrees with all of the records.

Examples

Example 1

Input
hikers = [[170, 0], [162, 1], [175, 0], [162, 2], [168, 2]]
Output
[[170, 0], [162, 1], [162, 2], [175, 0], [168, 2]]

Walking the returned line from the front: the hiker of 170 has nobody in front, so 0; the first hiker of 162 has the 170 in front, so 1; the second hiker of 162 has the 170 and the other 162 in front, so 2; the hiker of 175 has nobody as tall in front, so 0; the hiker of 168 has the 170 and the 175 in front, so 2. All five counts match their records.

Example 2

Input
hikers = [[150, 1], [150, 0], [150, 2]]
Output
[[150, 0], [150, 1], [150, 2]]

All three hikers are the same height, so each counts the ones in front of them. The counts 0, 1 and 2 fix the order from front to back.

Example 3

Input
hikers = [[172, 0], [172, 1], [165, 2], [180, 0], [165, 3], [172, 2]]
Output
[[172, 0], [172, 1], [165, 2], [165, 3], [172, 2], [180, 0]]

In the returned line the three hikers of 172 sit at positions 0, 1 and 4, with 0, 1 and 2 hikers as tall as them in front, and the two of 165 sit at positions 2 and 3, with 2 and 3 in front. The hiker of 180 sits last, and nobody in front is as tall, which matches their record of 0.

Constraints

  • 1 <= hikers.length <= 2000
  • hikers[i].length == 2
  • 0 <= height <= 10^6
  • 0 <= ahead < hikers.length
  • Exactly one line agrees with every record.

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 rebuild_line(hikers: list[list[int]]) -> list[list[int]]:
Java
public int[][] rebuildLine(int[][] hikers)

More on the same topics