Better Explanation Of Order of People Heights Problem And Java Program To Solve It

by

We will be solving LeetCode problem “406. Queue Reconstruction by Height” here. The problem states that:

You are given an array of people, “people“, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi. Reconstruct and return the queue that is represented by the input array “people“. The returned queue should be formatted as an array “queue“, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Input: people = [[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:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

I will discuss a simple approach. Anyways the approach will satisfy the LeetCode acceptance criteria on time & memory bounds.

  • First, we will sort “people” array in ascending order of heights. So input array becomes [[4, 4], [5, 0], [5, 2], [6, 1], [7, 0], [7, 1]].
  • We will create a new array named “queue” which we will use to store final positions of the persons based on the requirements mentioned above. “queue” array is empty at first & we have populated it with dummy values “-1”. Initial state of “queue” array is [[-1, -1], [-1, -1], [-1, -1], [-1, -1], [-1, -1], [-1, -1]].
  • Now we will start a loop & iterate over all the elements of the sorted input array one by one.
    • The first element [4, 4] is the shortest. The height is 4 & the person should have another 4 persons in front who are taller. So we put this element in 5th position of the “queue” array [[-1, -1], [-1, -1], [-1, -1], [-1, -1], [4, 4], [-1, -1]]. What did we gain by doing that? We found the final position of this element in the “queue” array. How? So we know that we need at least 4 elements which are taller than this element. So we kept four empty positions on the left hand side. Can we move the element one step on the right hand side? If we do that, we would need to fill the left hand side with one shorter element on top of the four taller elements that we already discussed. We know for sure that this element is the shortest one. So there is no shorter element available. That means we can’t move either to left side or to right hand side. So this is the fixed & final position of the shortest element.
    • Now we go to the second element of the sorted “people” array in the next iteration. That is the second shortest element in the array. We can remove the previous element from the scenario as we have already found its final position. So this element becomes the shortest element among the remaining active elements. That means we can apply the same logic that we discussed in first iteration. But one additional thing we need to remember. Our “queue” array is partially full now. So we need to run one inner loop from the beginning of the “queue” array & count empty slots so that it matches the required number of taller persons in front of it. As we are looping in ascending order, taller elements will come in next iterations only. So we need empty slots to put them on the left side of current element. Also, eligible persons positioned before a particular person might be taller or equal as mentioned in the problem statement. We haven’t considered equal part yet. Equal height elements can already be present in “queue” array via previous iterations. So we need to consider them too. So required number of eligible persons would be determined by summation of empty slots and already present equal height elements. You can see these conditions in the Java code below.
    • We need to follow the same logic till we finish iterating over all the elements using the loop.
  • After loop is complete, all elements will be in their final correct positions in the “queue” array.

Time Complexity: We are sorting the input array. It takes O(n log n) time with any standard sorting algorithm. Then we are having a outer loop & an inner loop. So overall time complexity would be O(n log n + n ^ 2).

Space Complexity: We are using an extra array to store results for n number of persons. So space complexity for this solution would be O(n).

You can find the complete Java code solution of this LeetCode problem below.

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        int[][] queue = new int[people.length][2];
        for(int[] person : queue){
            person[0] = -1;
        }
        
        Arrays.sort(people, (p1, p2) -> Integer.compare(p1[0], p2[0]));
        
        for(int[] person : people){
            int height = person[0];
            int pos = person[1];
            
            int infront = 0;
            int i = 0;
            while(pos > infront || queue[i][0] != -1){
                if(queue[i][0] == -1 ||  queue[i][0] == height){
                    infront++;
                }
                i++;
            }
            
            queue[i][0] = height;
            queue[i][1] = pos;
        }
        return queue;
    }
}

Leave a Comment