145. Queue Reconstruction by Height
Arrange the people so that each person's k equals the number of people before them whose heights are at least that person's height. Every input occurrence must appear once.
Equal heights contribute to the count. The contract also covers infeasible descriptions and the required ownership of returned rows.
Example 1
Input
people=[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Explanation: Each final prefix contains exactly the stated number of people at least as tall.
Example 2
Input
people=[[6,0],[5,0]]
Output
[[5,0],[6,0]]
Explanation: Inserting the shorter person at zero does not change the taller person’s qualifying count.
Example 3
Input
people=[[5,0],[5,0]]
Output
IllegalArgumentException
Explanation: Two equally tall people cannot both have zero equally-or-taller predecessors.
Constraints
0 <= people.length <= 2000people[i].length == 20 <= height <= 231 - 10 <= k < people.length- Return a feasible arrangement of the same people. Infeasible constraints raise an error.
Hints
Hint 1
In what processing order would every already placed person count toward the current k?
Hint 2
If every existing person qualifies, where should a new person with count k be inserted?
Hint 3
Sort by descending height and ascending k, insert at k, then verify feasibility under the stated contract.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Insert shorter people without disturbing taller counts
[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]