406. Queue Reconstruction by Height

Description

The problem requires reconstructing a queue of people based on two attributes. Each person is represented as a pair of integers where:

• people[i][0] is the height of the person.
• people[i][1] is the number of people in front of them who have a height greater than or equal to theirs.

The task is to return the queue after reconstructing it based on these two attributes.

Intuition

To solve this problem, the key observation is that sorting the people by their height in descending order helps us reconstruct the queue more easily. Once we have sorted people by height, we can place them in the correct position in the queue based on how many people should be in front of them. This way, we ensure that taller people are placed first, and shorter people are inserted in the appropriate positions without needing to shift larger heights.

Approach

1. Sort the people: - Sort the array by height in descending order (people[i][0]), and if two people have the same height, sort by the number of people in front of them (people[i][1]) in ascending order.
2. Reconstruct the queue: - Initialize an empty result list. - For each person in the sorted array, insert them into the result list at the index specified by people[i][1]. This ensures that the correct number of taller or equally tall people are placed in front of the person.
3. Return the result list.

Complexity

Time Complexity:

• Sorting the array takes O(n log n) where n is the number of people.
• Inserting each person into the queue takes O(n) in the worst case, as each insertion can shift the elements of the list.
• Thus, the overall time complexity is O(n^2) due to the insertions.

Space Complexity:

• The space complexity is O(n) for storing the result list.

Code

C++

class Solution {
public:
    vector> reconstructQueue(vector>& people) {
        vector> ans;
        // Sort by height in descending order, if same height then by the number of people in ascending order
        sort(people.begin(), people.end(), [](const vector& a, const vector& b) {
            return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
        });
        // Insert people in the result vector at the correct position
        for (auto& person : people) {
            ans.insert(ans.begin() + person[1], person);
        }
        return ans;
    }
};

Python

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        ans = []
        # Sort by height in descending order, if same height then by the number of people in ascending order
        people.sort(key=lambda x: (-x[0], x[1]))
        # Insert people in the result list at the correct position
        for person in people:
            ans.insert(person[1], person)
        return ans

Java

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        List ans = new LinkedList<>();
        // Sort by height in descending order, if same height then by the number of people in ascending order
        Arrays.sort(people, (a, b) -> b[0] == a[0] ? a[1] - b[1] : b[0] - a[0]);
        // Insert people in the result list at the correct position
        for (int[] person : people) {
            ans.add(person[1], person);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

JavaScript

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function (people) {
    let ans = []
    people.sort((a, b) => b[0] - a[0] || a[1] - b[1])
    people.forEach(val => {
        ans.splice(val[1], 0, val)
    })
    return ans
};