LeetCode 406. Queue Reconstruction by Height

Problem Statement

I have screenshot the problem statement on LeetCode. I think it’s always helpful to paraphrase the problem statement so that I could understand the problem better.

We are given a n x 2 matrix (or an array of arrays), where each row encodes the information about a person and can be written as [h, k]. h is the height of that person and k is the number of taller or equally tall people standing in front of that person in the resulting queue.

Let’s demonstrate this with the example. We are given:

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

The output is:

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

Consider the third person in the array. Their height is 5, and there are 2 taller people standing in front of them. Consider the next person in the array. Their height is 6, so only the second person is taller than them. This is because their encoding is [6,1].

Solution

Thought Process

So how do we approach this problem? It doesn’t sound really intuitive.

Recall that each person is encoded as [h, k]. When I think about the problem, if we only have people of the same heights, then k is exactly their positions in the returned array.

For example, if we are given only [7,0] and [7,1], then we need to return [[7,0],[7,1]]. k is exactly the index of those people!

Now, if we are given new information about a shorter person, such as [6,1], we can insert that person into the array [[7,0],[7,1]]. But where to insert that person? We know that the person is currently the shortest of all, and there should only be one taller person standing in front of them. Then, the index of [6,1] in the array is 1 because there should be only 1 person taller than them, and all people in the array are already taller.

This means we insert [6,1] at index 1 and get [[7,0], [6,1], [7,1]]. It works!

Solution

We can deduce that the algorithm is to place the tallest people first based on their k. Then move on to the second tallest people. Keep doing this until everyone has been inserted into the reconstructed queue.

More concisely, there are two steps:

Step 1: Sort the people based on heights in descending order. If they have the same heights, sort them based on their index in ascending order. We sort the people with the same heights in ascending order index-wise because we want smaller index people come before others of the same height.
In the example, after sorting, we should get:
[[7,0], [7,1], [6,1], [5,0], [5,2]]

Step 2: Add the person to the resulting array one by one. This is exactly similar to adding the tallest group first, and then the second tallest group (We are adding them one by one anyway in each group). k is the index where each person should be.

Code

Let’s walk through the code together.

Step 1: Sort the people.

We need to write a comparator to do this (see comments for more details):

Arrays.sort(people, new Comparator <int[]>() {
   @Override
   public int compare(int[] person1, int[] person2) {
       if (person1[0] != person2[0]) {
           // Descending order of height
           return person2[0] — person1[0]; 
       } else {
       // Same height, sort based on
       // ascending order of index (k)
       return person1[1] — person2[1];
       }
   }
});

Note that using this syntax can improve runtime:

Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0]-a[0] : a[1] — b[1]);

I decided to write down both ways because the former one is easier to understand.

Step 2: Add them one by one with k as the index
Step 2a: Use an ArrayList so that we don’t have to manually adjust shifting.

List<int[]> reconstructed= new ArrayList<int[]>();
// Note that people has already been sorted
for (int i = 0; i < people.length; i++) {
     reconstructed.add(people[i][1], people[i]);
     // add people[i] to its correct position based on k or 
     // people[i][1]
 }

Step 2b: Make an array out of the arraylist because we need to return an array of array (or a people.length x 2 matrix).

return reconstructed.toArray(new int[people.length][2]);

We solved the problem with these 2 steps! Awesome!

Analysis

Sorting can be seen as taking O(nlogn), where n is the length of the given array, or the number of people.

When we add people to our ArrayList, the operation takes O(n²) because we may need to shift the elements to insert new ones.

Then, time complexity is O(n²).

We create a new matrix to return the result, so space complexity is O(n).

Comments

I hope this step-by-step explanation is helpful to someone. Sometimes I struggle to understand all parts of the code when reading solutions, so I hope being really clear about the code is useful. I refer to https://evelynn.gitbooks.io/google-interview/queue-reconstruction-by-height.html and https://leetcode.com/problems/queue-reconstruction-by-height/discuss/701738/JAVA-Detailed-Explanation-w-code to understand and form the solution. Thank you for reading!