Queue Reconstruction by Height

Share

Reconstruct queue from [[h,k]] pairs where k = number of people with height >= h in front.

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]]
Example 2
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]]

Solution Approach

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
Java
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)