0670MediumArrayBinary Indexed TreeSegment TreeSorting

Rebuild the Photo Line

Tracked in this browser only

Trains the technique from

LeetCode 406Queue Reconstruction by Height

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def rebuild_line(hikers: list[list[int]]) -> list[list[int]]:

Java

public int[][] rebuildLine(int[][] hikers)

The intended approach

Time O(n^2): sorting is O(n log n) and each of the n insertions shifts up to n entries.Space O(n) for the sorted order and the line that is returned.

Sort the records by height from tallest down, and among equal heights by the recorded count from smallest up. Walk that order and insert each record into a growing list at the index its count names. Everyone already in the list is at least as tall as the hiker being inserted, so the count of taller-or-equal hikers in front of them is exactly the number of records sitting before that index, and inserting shifts only records that are taller or equal and already counted.

Pythonentry point: rebuild_line

def rebuild_line(hikers):
    # tallest first, so an insertion at index `ahead` cannot disturb anyone placed already
    order = sorted(hikers, key=lambda rec: (-rec[0], rec[1]))
    line = []
    for height, ahead in order:
        line.insert(ahead, [height, ahead])
    return line

The obvious version

Try every ordering of the records. For each one, walk it front to back and count, for every hiker, how many earlier hikers are at least as tall; keep the ordering only if every count matches the record. Return the smallest such ordering, which is the only one for a consistent set of records.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_rebuild_line(hikers):
    from itertools import permutations
    best = None
    for order in permutations(range(len(hikers))):
        line = [hikers[i] for i in order]
        good = True
        for j in range(len(line)):
            height = line[j][0]
            taller = 0
            for front in range(j):
                if line[front][0] >= height:
                    taller += 1
            if taller != line[j][1]:
                good = False
                break
        if good and (best is None or line < best):
            best = [list(rec) for rec in line]
    return best

How this problem was checked

Reference solution executed against 8 test cases — 8 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in