Queue Reconstruction by Height

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

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]);
  }
}