Problem Description

Given a list of people, each described by a pair of integers (h, k). Here h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. The task is to write a program to reconstruct the queue in the correct order.

Approach for Solution

The approach for solving this problem is to first sort the provided list of tuples in descending order of height (h), and in case of a tie, the values should be sorted in ascending order of k (number of people in front who are taller or equal in height to the current person). After sorting we'll get the tallest persons at the start of the queue and in case of persons of the same height, they will be arranged as per their k value.

With this sorted list, the task is to correctly place the persons. To do this, we pick up each person in the sorted list and place them at an index that matches their k value in the resultant list.

Walkthrough with example

Suppose the input is: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

After sorting by height in descending order and by k in ascending order, we will have: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

Now insert persons in the output list at correct positions:

1* Insert [7,0] at index 0: [[7,0]]
2* Insert [7,1] at index 1: [[7,0], [7,1]]
3* Insert [6,1] at index 1: [[7,0], [6,1], [7,1]]
4* Insert [5,0] at index 0: [[5,0], [7,0], [6,1], [7,1]]
5* Insert [5,2] at index 2: [[5,0], [7,0], [5,2], [6,1], [7,1]]
6* Insert [4,4] at index 4: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

So, the final output will be [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

And, the time complexity will be O(n^2) as for each person we need to access the corresponding index in the queue, which takes linear time.

Python Solution

1
2python
3class Solution:
4    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
5        # Sort the list
6        people.sort(key=lambda x: (-x[0], x[1]))
7        output = []
8        # Insert person on correct position
9        for p in people:
10            output.insert(p[1], p)
11        return output

Java Solution

1
2java
3class Solution {
4    public int[][] reconstructQueue(int[][] people) {
5        // Sort the array
6        Arrays.sort(people, (p1, p2) -> p1[0] != p2[0] ? Integer.compare(p2[0], p1[0]) : Integer.compare(p1[1], p2[1]));
7        List<int[]> output = new ArrayList<>();
8        // Insert person at correct position
9        for (int[] p : people) {
10            output.add(p[1], p);
11        }
12        return output.toArray(new int[0][0]);
13    }
14}

JavaScript Solution

1
2javascript
3var reconstructQueue = function(people) {
4    // Sort the array
5    people.sort((a, b) => b[0] == a[0] ? a[1] - b[1] : b[0] - a[0]);
6
7    let output = [];
8
9    // Insert person at correct position
10    for (let i = 0; i < people.length; i++) {
11        output.splice(people[i][1], 0, people[i]);
12    }
13    return output;
14};

C++ Solution

1
2cpp
3class Solution {
4public:
5    static bool comp(vector<int>& a,vector<int>& b){
6        if(a[0]==b[0]){
7            return a[1]<b[1];
8        }
9        return a[0]>b[0];  
10    }
11    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
12        // Sort vector
13        sort(people.begin(),people.end(),comp);
14        
15        vector<vector<int>> output;
16        // Insert person at correct position
17        for(int i=0;i<people.size();i++){
18            output.insert(output.begin()+people[i][1],people[i]);
19        }
20        return output;
21    }
22};

C# Solution

1
2csharp
3public class Solution {
4    public int[][] ReconstructQueue(int[][] people) {
5        // Sort the array
6        Array.Sort(people, (p1, p2) => p1[0] == p2[0] ? p1[1].CompareTo(p2[1]) : p2[0].CompareTo(p1[0]));
7        List<int[]> output = new List<int[]>();
8        // Insert person at correct position
9        foreach (var p in people)
10        {
11            output.Insert(p[1], p);
12        }
13        return output.ToArray();
14    }
15}

Conclusion

To reconstruct a queue with each person's height and the number of people in front of them, we can first sort the provided list of people based on their height and number of people in front. This sorted list will allow us to correctly arrange the people in the queue.

The Python, Java, JavaScript, C++ and C# solutions round off by picking up each person in the sorted list and inserting them at an index matching their 'k' value. This approach solves the problem with a time complexity of O(n^2), where 'n' represents the total number of people.

Each solution follows a similar logic despite different coding languages: sort the array according to the specific requirements, then iterate over the sorted list to correctly place each person in the output array or list.

Understanding these solutions can be beneficial for developers working on algorithms involving sorting and arranging elements based on more than one criteria. These solutions not only provide a path to resolve the current problem, but also provide insight on how to handle similar problems in future.