406. Queue Reconstruction by Height

MediumGreedyBinary Indexed TreeSegment TreeArraySorting

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 ith 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 their k 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 their k value. It works because by inserting the tallest people first, their k 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 the k 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 the k value in ascending order. The lambda function in the sort method accomplishes this by using -x[0] for descending height and x[1] for ascending k values. Sorting is done with this line:
```
people.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.
```
ans = []
```
Iterate over the sorted people array. For each person p, we insert them into the ans list at the index specified by their k value. This is possible because at the time of their insertion, there will be p[1] (which is k) taller or equal height people already in the list, since those have been inserted earlier due to the sorting strategy.
```
for p in people:
    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.
```
return 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 Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Suppose we are given the following array people:

people = [[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 and k value in ascending order when the heights are equal. After sorting, our people array looks like this:

people = [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

We initialize an empty list ans:

ans = []

We then iterate over the sorted people array and insert each person into the ans list at the index specified by their k value:
- We insert [7, 0] at index 0: ans = [[7, 0]]
- We insert [7, 1] at index 1: ans = [[7, 0], [7, 1]]
- We insert [6, 1] at index 1: ans = [[7, 0], [6, 1], [7, 1]]
- We insert [5, 0] at index 0: ans = [[5, 0], [7, 0], [6, 1], [7, 1]]
- We insert [5, 2] at index 2: ans = [[5, 0], [7, 0], [5, 2], [6, 1], [7, 1]]
- Finally, we insert [4, 4] at index 4: ans = [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
The final ans list is our reconstructed queue which aligns with the original people array attributes:

ans = [[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 of O(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 of O(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 is O(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don't know