Reconstruct queue from [[h,k]] pairs where k = number of people with height >= h in front.
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]]
Input: people=[[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] → Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
Sort tallest first (descending height, ascending k). Insert each person at index k.
- Sort by height descending, k ascending
- For each person insert at position k in result list
- Taller people are already placed; inserting at k gives correct position
- Return result list
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
List<int[]> list = new ArrayList<>();
for (int[] p : people) list.add(p[1], p);
return list.toArray(new int[people.length][]);
}
- Time Complexity: O(n^2)
- Space Complexity: O(n)