406. Queue Reconstruction by Height – Leetcode Solutions

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

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # Step 1: Sort the array
        # Sort by height in descending order, then by k in ascending order
        people.sort(key=lambda x: (-x[0], x[1]))
        
        # Step 2: Reconstruct the queue
        queue = []
        for person in people:
            height, k = person
            # Insert person at index k
            queue.insert(k, person)
        
        return queue

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        // Sort the input array.
        // First, sort by height in descending order.
        // If heights are equal, sort by the number of people in front (k) in ascending order.
        sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0]) {
                return a[1] < b[1];
            }
            return a[0] > b[0];
        });

        // Initialize the resulting queue
        vector<vector<int>> result;

        // Insert each person into the result based on their k value.
        for (const auto& person : people) {
            result.insert(result.begin() + person[1], person);
        }

        return result;
    }
};

var reconstructQueue = function(people) {
    // Step 1: Sort the array
    // Sort by height in descending order (hi) and by ki in ascending order for people with the same height
    people.sort((a, b) => {
        if (a[0] === b[0]) {
            return a[1] - b[1]; // If heights are the same, sort by ki
        }
        return b[0] - a[0]; // Otherwise, sort by height in descending order
    });

    // Step 2: Initialize an empty array to hold the reconstructed queue
    const queue = [];

    // Step 3: Insert each person into the queue
    // Use the ki value to determine the index at which the person should be inserted
    for (const person of people) {
        queue.splice(person[1], 0, person);
    }

    // Step 4: Return the reconstructed queue
    return queue;
};

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // Step 1: Sort the input array
        // Sort by height in descending order, and for equal heights, sort by the number of people (k) in ascending order.
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1]; // Sort by k (ascending) when heights are equal
            } else {
                return b[0] - a[0]; // Sort by height (descending)
            }
        });

        // Step 2: Insert each person into the result list based on their k-value
        List<int[]> result = new ArrayList<>();
        for (int[] person : people) {
            result.add(person[1], person); // Insert person at the index equal to their k-value
        }

        // Step 3: Convert the result list back to a 2D array
        return result.toArray(new int[result.size()][]);
    }
}