Queue Reconstruction by Height

Updated on 04 July, 2025
Queue Reconstruction by Height header image

Problem Statement

In this problem, we are provided with an array people, where each element people[i] consists of a pair [hi, ki]. Here, hi denotes the height of the i-th person, and ki represents the number of individuals standing in front of this person who are of equal or greater height than hi. The objective is to reconstruct the queue from this unordered list. Each element in the output queue, queue[j] = [hj, kj], must satisfy the criteria that there are exactly kj people in front of person j with height hj or taller. The goal is to return this reconstructed queue as an array where queue[0] is the front of the queue.

Examples

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:

Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

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

Constraints

  • 1 <= people.length <= 2000
  • 0 <= hi <= 106
  • 0 <= ki < people.length
  • It is guaranteed that the queue can be reconstructed.

Approach and Intuition

The problem requires reconstructing the queue based on height and the count of people taller or of the same height standing in front. This is a sorting and placement problem where understanding the interdependencies of array items (heights and counts) is crucial.

  • Sort and Insert Approach:

    1. First, sort the people array in descending order based on height h. If two people have the same height, sort them by increasing order of k.
    2. Once sorted, initialize an empty list queue.
    3. For each person [h, k] from the sorted list, insert them into the queue at the index k. In Python, this can be done using queue.insert(k, [h, k]).
    4. The rationale behind insertion at index k is that there should be exactly k people before this person who are of the same or greater height.
    5. By placing the tallest people first, we ensure that inserting subsequent people does not affect the counts of those already placed.
  • Visualization and Examples:

    • In example 1, start by sorting people resulting in [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]].
    • Start inserting from the sorted array: place [7, 0] at index 0, and so on. Each insertion respects the positional requirements dictated by k.
    • For example 2, after sorting and inserting in similar fashion, the structure of the queue gradually builds up correctly without violating the k constraints.

By using this sort and insertion methodology, each placement ensures the condition that the number of people standing in front with equal or greater height matches the k value of the person being placed, satisfying the problem's constraints and requirements.

Solutions

  • Java
java
class Solution {
  public int[][] arrangeQueue(int[][] queue) {
    Arrays.sort(queue, new Comparator<int[]>() {
      @Override
      public int compare(int[] item1, int[] item2) {
        return item1[0] == item2[0] ? item1[1] - item2[1] : item2[0] - item1[0];
      }
    });
    
    List<int[]> result = new LinkedList<>();
    for(int[] person : queue){
      result.add(person[1], person);
    }
    
    int length = queue.length;
    return result.toArray(new int[length][2]);
  }
}

The solution provided is a Java implementation for reconstructing a queue based on height and the number of people in front of an individual who have an equal or greater height.

  • Start with sorting the given array of people using a custom comparator. The array queue contains elements where queue[i][0] is the height of the person and queue[i][1] is the count of people taller or of the same height standing in front of this person.
  • The comparator prioritizes by height (descending order), and, if the heights are equal, it sorts by the count of people in ascending order.
  • Initialize a LinkedList to facilitate easier insertions at specific indices as you iterate through the sorted array.
  • For each person in the sorted array, insert them into the LinkedList at the index specified by their count (i.e., person[1]), effectively placing them in the correct position relative to those already inserted.
  • Convert the LinkedList to a 2D array matching the dimensions of the input queue and return this as the final reconstructed queue.

By sorting the people by height and then respecting the count of people in front, this approach efficiently reconstructs the order in which people should stand to satisfy the given conditions.

Comments

No comments yet.