Queue Reconstruction by Height

We are given a list of people described by height h and a number k. k refers to the number of people in front of this person who are of height greater than or equal to their height. We have to write an algorithm to reconstruct the queue.

The number of people will be less than 100.

Input:
[[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:

[7, 0] – Height = 7 and there should be 0 people equal in height or taller in front of this person

[4, 4] – Height = 4 and there should be 4 people equal in height or taller in front of this person

[7, 1] – Height = 7 and there should be 1 people equal in height or taller in front of this person

[5, 0] – Height = 5 and there should be 0 people equal in height or taller in front of this person

[6, 1] – Height = 6 and there should be 1 people equal in height or taller in front of this person

[5, 2] – Height = 5 and there should be 2 people equal in height or taller in front of this person

Solution:

There are two elements in each list item which is the height and k.

Input = [[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]]

Let’s manually try to place the people in a queue. The given list looks like this.

We first take the tallest person and place them in the queue according to their index value. If two people have the same index value, then we give priority to the person who is shorter. We will see why in a bit. So the queue will look like this after placing [7, 0] and [7, 1].

Next, we pick the next tallest person in queue [6, 1]. When we try to place them in the index 1, there is already a person of height 7 there. In this case, we need to place the person with the shorter height in front because they should have only 1 more person who is of equal height or is taller than them. We insert this person in the queue before [7, 1]. The queue will now look like this.

We can pick the next tallest person with height 5. We can place [5, 0] before placing [5, 2] since the lower index person gets priority. 0th index already has a person of height 7, but we will push them back and insert [5, 0] to let the shorter person be in the front. The queue will now look like this.

Let’s continue doing this for the left out elements and we will get the following.

The code for this algorithm involves two steps:

• Arrange people in descending height. When there is a tie in height, give priority to the one with the lower index.
• Insert people according to their indexes into a new queue. When there is a tie in index, give priority to the one with the lower height.

Time Complexity: O(NlogN) for sorting and O(N) to insert an element into a list, so the overall complexity to insert N elements will be O(N²).

Space Complexity: We will do the sorting in place and the result queue need not be considered as extra space, so space complexity is O(1).

Code for the above solution:

def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:

    # sort people by descending height and ascending index k
    people.sort(key = lambda x: (-x[0], x[1]))

    results = [] * len(people)

    for p in people:
        results.insert(p[1], p)

    return results

Hope you enjoyed reading this post. Have a great day!