406. Queue Reconstruction by Height
Problem Description
In this problem, we are given an array of people's attributes, where each person is represented by a pair of values [h, k]
. The h
represents the height of the person and k
represents the number of people who are in front of this person in a queue and are taller or of the same height. The array people
does not necessarily represent the order of people in a queue. Our task is to reconstruct the queue in such a way that the attributes of people in the reconstructed queue align with the original array people
. The reconstructed queue should also be represented as an array where each element follows the same pair representation [h, k]
, with each pair denoting the attributes of the people in the queue.
To be more concrete, if people[i] = [h_i, k_i]
, we need to place the i
th person in such a position in the queue that k_i
is the exact count of people ahead of this person with heights greater than or equal to h_i
.
Intuition
The intuition behind the solution lies in the fact that it's easier to place the tallest people first and then insert the shorter people at their appropriate positions based on the k
value. Here's how we can think of the approach:
-
Sort
people
by their height in descending order; if two people have the same height, sort them by theirk
value in ascending order. This way, we start with the tallest people, and for those with the same height, we place those with fewer people in front first. -
Initialize an empty list
ans
that will represent our queue. -
Iterate over the sorted list, inserting each person into the
ans
list at the index equal to theirk
value. It works because by inserting the tallest people first, theirk
value corresponds exactly to the position they should be in the queue. As we insert the shorter people, we displace the taller ones only if needed, which maintains the integrity of thek
values.
By following this approach, we ensure that each person is placed in accordance with the number of taller or equally tall people that are supposed to be in front of them according to the original array people
.
Learn more about Greedy, Segment Tree and Sorting patterns.
Solution Approach
The solution uses a greedy algorithm approach along with list operations to reconstruct the queue. Here is a step-by-step walkthrough of the implementation based on the solution code provided:
-
Sort the
people
array in a way such that we first sort the people by height in descending order and then, if the heights are equal, sort by thek
value in ascending order. The lambda function in thesort
method accomplishes this by using-x[0]
for descending height andx[1]
for ascendingk
values. Sorting is done with this line:1people.sort(key=lambda x: (-x[0], x[1]))
By sorting in this manner, we prioritize taller individuals and, among those of identical height, prioritize those with a smaller
k
value, which is the count of people in front of them. -
Initialize an empty list
ans
which will be used to construct the queue.1ans = []
-
Iterate over the sorted
people
array. For each personp
, we insert them into theans
list at the index specified by theirk
value. This is possible because at the time of their insertion, there will bep[1]
(which isk
) taller or equal height people already in the list, since those have been inserted earlier due to the sorting strategy.1for p in people: 2 ans.insert(p[1], p)
The
insert
operation places the person at the correct position in the queue, shifting elements that are already there. -
Return the
ans
list which now represents the reconstructed queue.1return ans
Using this greedy strategy, we are able to re-order the array so that each person is positioned in accordance with their height and the count of people in front of them with equal or greater height. The use of sorting and list insertions are key aspects of the algorithm, ensuring that the resulting ans
list satisfies the requirements that are stated in the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach.
Suppose we are given the following array people
:
1people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
Following the steps outlined in the solution approach:
- We first sort the array
people
by height in descending order andk
value in ascending order when the heights are equal. After sorting, ourpeople
array looks like this:
1people = [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
- We initialize an empty list
ans
:
1ans = []
-
We then iterate over the sorted
people
array and insert each person into theans
list at the index specified by theirk
value:- We insert
[7, 0]
at index0
:ans = [[7, 0]]
- We insert
[7, 1]
at index1
:ans = [[7, 0], [7, 1]]
- We insert
[6, 1]
at index1
:ans = [[7, 0], [6, 1], [7, 1]]
- We insert
[5, 0]
at index0
:ans = [[5, 0], [7, 0], [6, 1], [7, 1]]
- We insert
[5, 2]
at index2
:ans = [[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]
- Finally, we insert
[4, 4]
at index4
:ans = [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
- We insert
-
The final
ans
list is our reconstructed queue which aligns with the originalpeople
array attributes:
1ans = [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
Using the greedy solution approach of sorting the individuals by height and then inserting them into the queue based on their k
value, we have successfully reconstructed a queue that satisfies the requirements of the problem. In this queue, for every person, the k
value is the exact count of people ahead of them with heights greater than or equal to their own.
Solution Implementation
1from typing import List
2
3class Solution:
4 def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
5 # Sort the 'people' array in descending order of height (h),
6 # and in the case of a tie, in ascending order of the number of people in front (k).
7 people.sort(key=lambda person: (-person[0], person[1]))
8
9 # Initialize an empty list to hold the final queue reconstruction
10 queue = []
11
12 # Iterate over the sorted 'people' list
13 for person in people:
14 # Insert each person into the queue. The index for insertion is the k-value,
15 # which represents the number of people in front of them with equal or greater height.
16 queue.insert(person[1], person)
17
18 # Return the reconstructed queue
19 return queue
20
1import java.util.Arrays;
2import java.util.ArrayList;
3import java.util.List;
4
5class Solution {
6
7 public int[][] reconstructQueue(int[][] people) {
8 // Sort the array. First, sort by height in descending order.
9 // If heights are equal, sort by the number of people in front (k-value) in ascending order.
10 Arrays.sort(people, (person1, person2) ->
11 person1[0] == person2[0] ? person1[1] - person2[1] : person2[0] - person1[0]);
12
13 // Initialize a list to hold the final queue reconstruction,
14 // which allows us to insert people at specific indices.
15 List<int[]> reconstructedQueue = new ArrayList<>(people.length);
16
17 // Iterate over the sorted array, and insert each person into the list
18 // at the index specified by their k-value.
19 for (int[] person : people) {
20 // The second value of each person array (person[1])
21 // specifies the index at which this person should be added in the queue
22 reconstructedQueue.add(person[1], person);
23 }
24
25 // Convert the list back to an array before returning it.
26 return reconstructedQueue.toArray(new int[reconstructedQueue.size()][]);
27 }
28}
29
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 std::vector<std::vector<int>> reconstructQueue(std::vector<std::vector<int>>& people) {
7 // Sort the people to arrange them according to their height in descending order.
8 // If two people are of the same height, order them by their "k-value" in ascending order.
9 std::sort(people.begin(), people.end(), [](const std::vector<int>& personA, const std::vector<int>& personB) {
10 return personA[0] > personB[0] || (personA[0] == personB[0] && personA[1] < personB[1]);
11 });
12
13 // Initialize an empty vector for the final arrangement.
14 std::vector<std::vector<int>> arrangedQueue;
15
16 // Insert each person into the arrangedQueue.
17 // The index to insert the person is determined by the person's "k-value",
18 // which indicates the number of people in front of this person who have a height greater than or equal to this person's height.
19 for (const std::vector<int>& person : people) {
20 arrangedQueue.insert(arrangedQueue.begin() + person[1], person);
21 }
22
23 // Return the final arrangement of the queue.
24 return arrangedQueue;
25 }
26};
27
1function reconstructQueue(people: number[][]): number[][] {
2 // Sort the `people` array to arrange them by their height in descending order.
3 // If two people have the same height, order them by their k-value in ascending order.
4 people.sort((a, b) => {
5 return b[0] - a[0] || a[1] - b[1];
6 });
7
8 // Initialize an empty array for the final arrangement.
9 let arrangedQueue: number[][] = [];
10
11 // Insert each person into the `arrangedQueue`.
12 // The index at which to insert is determined by the person's k-value,
13 // which indicates the number of people in front of them with a height greater than or equal.
14 for (let person of people) {
15 arrangedQueue.splice(person[1], 0, person);
16 }
17
18 // Return the final arrangement of the queue.
19 return arrangedQueue;
20}
21
22// Example of usage:
23// let peopleInput: number[][] = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]];
24// let queue = reconstructQueue(peopleInput);
25// console.log(queue); // Outputs arranged queue based on the given conditions.
26
Time and Space Complexity
Time Complexity
The time complexity of the code can be broken down into two major operations:
-
Sorting the
people
array:This operation uses a sorting algorithm, typically Timsort in Python, which has a time complexity of
O(n log n)
for an array of n elements. -
Reconstructing the queue by inserting elements:
The
insert
operation within a list has a time complexity ofO(n)
in the worst case because it may require shifting the elements of the list.Since
insert
is called for each person in the sorted array and the list can grow up to n elements, this operation will have a worst-case complexity ofO(n^2)
as it performs n insertions into a structure that can be up to n in size.
By combining these, the overall time complexity of the code is O(n log n) + O(n^2)
, which simplifies to O(n^2)
since O(n^2)
is the dominating term when n is large.
Space Complexity
The space complexity of the code is the amount of extra space used by the algorithm, not counting the space occupied by the input itself. In this case:
-
Sorted
people
array:Since the sorting operation is done in-place, it does not contribute to additional space complexity beyond what is taken by the input
people
array. -
The
ans
list:This list is created to store the output and grows to contain n elements, which are the same elements from the input
people
array. Thus, the space required isO(n)
.
Therefore, the overall space complexity of the code is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced