Line Up by Height Tags
MediumSorting & Searching
Problem
Visitors at a theme park queued up, then scattered. Each wrote down a tag [height, ahead]: their height in centimetres and how many people standing in front of them were at least as tall.
Given the shuffled tags people, rebuild the original queue from front to back and return it as a list of tags. The input always comes from a real queue, so exactly one answer exists.
Example 1
- Input:
- people = [[160, 0], [175, 0], [175, 1], [150, 2], [165, 2]]
- Output:
- [[160, 0], [175, 0], [150, 2], [175, 1], [165, 2]]
The 150 cm visitor has 160 and 175 in front (2 at least as tall). The second 175 has the first 175 in front.
Example 2
- Input:
- people = [[170, 2], [190, 0], [170, 1], [180, 0]]
- Output:
- [[180, 0], [170, 1], [170, 2], [190, 0]]
Constraints
- 1 ≤ people.length ≤ 2000
- 100 ≤ height ≤ 250
- 0 ≤ ahead < people.length
- The tags describe a valid queue.
Hint
Show the first hint
Shorter people are invisible to taller people's counts. Who should you place first?
Walkthrough
How to approach it
01Clarify before coding
- Does 'at least as tall' include equal heights? Yes, which matters for ties.
- Is the answer unique? Yes, the tags come from a real queue and determine it.
- How large? Up to 2000 people, so O(n²) insertion is acceptable.
02Brute force
Try every permutation and check whether all counts match.
Cost: O(n! · n²): impossible.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.