Code Implementation

class Solution:
    def reconstructQueue(self, people):
        # Sort by descending height, then ascending k-value
        people.sort(key=lambda x: (-x[0], x[1]))
        queue = []
        for person in people:
            queue.insert(person[1], person)
        return queue
      

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] != b[0] ? a[0] > b[0] : a[1] < b[1];
        });
        vector<vector<int>> queue;
        for (const auto& person : people) {
            queue.insert(queue.begin() + person[1], person);
        }
        return queue;
    }
};
      

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> {
            if (a[0] != b[0]) return b[0] - a[0];
            return a[1] - b[1];
        });
        List<int[]> queue = new ArrayList<>();
        for (int[] person : people) {
            queue.add(person[1], person);
        }
        return queue.toArray(new int[people.length][]);
    }
}
      

var reconstructQueue = function(people) {
    people.sort((a, b) => {
        if (a[0] !== b[0]) return b[0] - a[0];
        return a[1] - b[1];
    });
    const queue = [];
    for (const person of people) {
        queue.splice(person[1], 0, person);
    }
    return queue;
};
      

Problem Description

You are given a list of people, where each person is represented as a pair [h, k]:

• h is the person's height
• k is the number of people in front of this person who have a height greater than or equal to h

Thought Process

At first glance, you might think to try every possible arrangement and check if the constraints are satisfied. However, with n people, this would require checking n! permutations, which is extremely inefficient.

Instead, we can look for patterns or properties in the constraints. Since k counts how many people of at least the same height are in front, it suggests that taller people should be placed first, as their position is not affected by shorter people. This insight allows us to shift from brute-force to a more optimized and structured approach.

Solution Approach

• Step 1: Sort the people. Sort the list in descending order by height (h). For people with the same height, sort them by ascending k value. This ensures that taller people are placed before shorter ones, and among those with the same height, those with fewer people in front come first.
• Step 2: Insert into the queue. Initialize an empty list to represent the queue. Iterate through the sorted list, and for each person, insert them at the index equal to their k value. This works because when we insert a person, all people already in the queue are either taller or have the same height, so their k value is correct.
• Step 3: Return the queue. After all insertions, the queue will satisfy all constraints. Each person's k value is preserved, and the order is valid.

We use a list/array because insertions at arbitrary positions are efficient enough for the problem constraints. Sorting ensures correctness, and the insert operation maintains the required order.

Example Walkthrough

Let's walk through the sample input: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

1. Sort: After sorting by height descending and k ascending:
   • [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
2. Insert into queue:
   • Insert [7,0] at index 0: [[7,0]]
   • Insert [7,1] at index 1: [[7,0], [7,1]]
   • Insert [6,1] at index 1: [[7,0], [6,1], [7,1]]
   • Insert [5,0] at index 0: [[5,0], [7,0], [6,1], [7,1]]
   • Insert [5,2] at index 2: [[5,0], [7,0], [5,2], [6,1], [7,1]]
   • Insert [4,4] at index 4: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
3. Final queue: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

At each step, the k value is satisfied because all previously inserted people are as tall or taller.

Time and Space Complexity

• Brute-force approach: Would require checking all n! permutations, which is computationally infeasible for even moderate values of n.
• Optimized approach:
  • Time Complexity: Sorting takes O(n \log n). Each insertion into a list at an arbitrary position takes O(n), and we do this for each of the n people, making the insertion step O(n^2) in total.
  • Space Complexity: We use O(n) extra space to build the output queue.

Summary

The key insight is to process people from tallest to shortest, inserting each at their k index. This ensures that the number of taller people in front of each person matches their k value. By leveraging sorting and list insertion, we achieve a solution that's both elegant and efficient compared to brute-force, making this a classic example of a greedy algorithm with careful ordering.