Rebuild the Photo Line
MediumGreedy
Problem
A class photo was taken with everyone standing in a single line, but the line got shuffled. For each person you still have a card [height, ahead]: ahead is how many people standing in front of them in the photo were at least as tall as they are.
Return the original line, front to back, as a list of cards. The cards always describe exactly one valid line.
Example 1
- Input:
- people = [[3, 3], [6, 0], [4, 2], [5, 0], [3, 1]]
- Output:
- [[5, 0], [3, 1], [6, 0], [3, 3], [4, 2]]
For the last person (height 4), the people in front with height ≥ 4 are 5 and 6: two of them.
Example 2
- Input:
- people = [[2, 0], [1, 1]]
- Output:
- [[2, 0], [1, 1]]
Constraints
- 1 ≤ people.length ≤ 2000
- 1 ≤ height ≤ 10^6
- 0 ≤ ahead < people.length
- A valid line always exists.
Hint
Show the first hint
Shorter people are invisible to taller people's counts. Who should be placed first?
Walkthrough
How to approach it
01Clarify before coding
- Does 'at least as tall' include equal heights? Yes, equal heights count.
- Is the answer unique? Yes, the cards determine exactly one line.
- How large is n? Up to 2000, so O(n²) insertion is acceptable.
02Brute force
Try every permutation and check each card's count.
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.