grid47 Exploring patterns and algorithms
Sep 27, 2024
5 min read
Solution to LeetCode 406: Queue Reconstruction by Height Problem
You are given an array of people, where each person is represented by two integers: their height hi and the number of people ki in front of them who have a height greater than or equal to hi. Your task is to reconstruct the queue based on these attributes.
Problem
Approach
Steps
Complexity
Input: You are given an array people where each element represents a person with their height and the number of people taller or of equal height in front of them.
Example: For people = [[6, 0], [5, 0], [4, 3], [3, 2], [2, 2], [1, 4]], the reconstructed queue is [[4, 3], [5, 0], [6, 0], [3, 2], [2, 2], [1, 4]].
Constraints:
• 1 <= people.length <= 2000
• 0 <= hi <= 10^6
• 0 <= ki < people.length
• It is guaranteed that the queue can be reconstructed.
Output: Return the reconstructed queue where each element represents a person with their height and the number of people taller or of equal height in front of them.
Example: For people = [[7, 0], [4, 2], [7, 1], [6, 0], [5, 1], [5, 2]], the reconstructed queue is [[7, 0], [5, 1], [6, 0], [5, 2], [7, 1], [4, 2]].
Constraints:
Goal: Reconstruct the queue by sorting the people by height in descending order and inserting each person based on their ki value.
Steps:
• 1. Sort the people in descending order based on their height. If two people have the same height, sort by their ki value in ascending order.
• 2. For each person, insert them at the index specified by their ki value in the current reconstructed queue.
• 3. Return the reconstructed queue.
Goal: The input satisfies the following constraints:
Steps:
• 1 <= people.length <= 2000
• 0 <= hi <= 10^6
• 0 <= ki < people.length
• It is guaranteed that the queue can be reconstructed.
Assumptions:
• The input list contains valid people data and can always be reconstructed into a valid queue.
• Input: For people = [[6, 0], [5, 0], [4, 3], [3, 2], [2, 2], [1, 4]], the reconstructed queue is [[4, 3], [5, 0], [6, 0], [3, 2], [2, 2], [1, 4]].
• Explanation: Sort the people by height in descending order and insert them into the queue based on their ki values.
Approach: Sort the people in descending order by height and insert them into the queue using their ki values to ensure the correct order.
Observations:
• The key observation is to sort the people first by their height and then by the ki value.
• After sorting the list, inserting each person at their respective position using their ki value will give the correct order.
Steps:
• 1. Sort the array of people first by height in descending order and then by ki value in ascending order.
• 2. Insert each person at the index specified by their ki value in the reconstructed queue.
• 3. Return the reconstructed queue as the result.
Empty Inputs:
Large Inputs:
• For large inputs, ensure that the sorting and insertion steps are efficient enough to handle up to 2000 people.
Special Values:
• The queue can be reconstructed even if the people are already in the correct order.
Constraints:
• The solution must handle inputs with varying heights and ki values, ensuring that the final queue meets the given conditions.
Define the function `reconstructQueue`, which takes a reference to a 2D vector `people` and returns a 2D vector with the reconstructed queue.
2 : Sorting
sort( people.begin(), people.end(), [] (vector<int> a, vector<int> b) {
Sort the `people` vector. The custom comparator sorts primarily by height (in descending order) and, if the heights are the same, by the number of people in front (in ascending order).
The sorting logic ensures that taller people come first. If two people have the same height, the one with fewer people ahead of them (based on the second value in the pair) comes first.
4 : Vector Initialization
vector<vector<int>> ans;
Initialize an empty 2D vector `ans` to store the reconstructed queue.
5 : For Loop
for(autop: people)
Start a `for` loop to iterate through each person `p` in the sorted `people` vector.
6 : Vector Insertion
ans.insert(ans.begin() + p[1], p);
Insert the person `p` at the correct position in the `ans` vector. The position is determined by the second value of the pair `p[1]`, which represents the number of people in front of them with greater or equal height.
7 : Return Statement
return ans;
Return the `ans` vector, which now contains the reconstructed queue.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is dominated by the sorting step, which is O(n log n).
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage required for the reconstructed queue.
