Queue Reconstruction By Height - Leetcode Solution

Problem Statement

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integer (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Example:

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]]

Solution

This problem is a bit tricky, but we can solve it by sorting the input array in a particular way. Let's say we sort the array in descending order of heights. If two people have the same height, then we can sort them in ascending order of k.

Once the array is sorted, we can iterate over it and insert each person into a new array at the index specified by k. Since we have sorted the array in such a way that all the people who are taller than the current person have already been inserted into the new array, we can be sure that the index k will be the correct index for the current person.

Let's look at an example to understand this better.

Example

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

First, we sort the array in the way described above. After sorting, the array looks like this:

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

Next, we create a new empty array of the same length as the input array. We iterate over the sorted array, and for each person, we insert them into the new array at the index specified by k. Here's what the new array looks like after each iteration:

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]]

And we're done! The output array is [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]].

Time Complexity

The time complexity of this solution is O(n^2) in the worst case, where n is the length of the input array. This is because we insert each person into the new array one at a time, which takes O(n) time in the worst case. However, in practice, the actual running time is much faster than this because the input array is sorted.

1