Better Explanation Of Order of People Heights Problem And Java Program To Solve It
Order of People Heights is an interview question that is asked in Google. You can find the question in websites like InterviewBit & CareerCup. But the problem is that you won't find a good explanation of the problem anywhere. Let me try to describe the problem statement clearly.
Input : Heights: 5 3 2 6 1 4 InFronts: 0 1 2 0 3 2
We have two input arrays of same size n. n is the number of people that we have. Now first array gives us the actual height of the person at index i. Second array gives us the number of taller persons who should be in front of i th person(left hand side of the index). There are no duplicates in the Heights array.
Index 0 : value (5, 0) is correct as no taller person is on left hand side
Index 1 : value (3, 1) is correct as only 5 is taller than 3
Index 2 : value (2, 2) is correct as 5 & 3 are on the left side of 2
Index 3 : value (6, 0) is correct as all left hand heights are less than 6
Index 4 : value (1, 3) is wrong as we have total 4 taller (5, 3, 2 & 6) heights instead of 3
Index 5 : value (4, 2) is correct as 5 & 6 are the two taller heights on the left hand side
We need to rearrange the heights so that it maintains the order correctly as per InFronts array. In the above example (1, 3) is not having the correct order.
Hope you have a better understanding of the problem now.
To solve this, first we will sort the heights from shortest to tallest.
Input : Heights: 1 2 3 4 5 6 InFronts: 3 2 1 2 0 0
From above, you can see 1 is the shortest height & it has been moved to index 0. Now we can take a empty array of size n & put 1 at (3+1) = 4 th position or 3rd index. Why? Because we need at least three empty positions before 1 to insert three taller elements. And we can't move 1 on the right hand side after 3rd index. Then we would have to fill that with a shorter element than 1 to maintain InFronts value of 3. But 1 is the shortest height & there is no other element which is shorter than that. That way, we can finalize the shortest height position. And then we can take the next shortest height & follow the same steps.
The final order would be
Heights : 5 3 2 1 6 4 Infronts: 0 1 2 3 0 2
We need to return only the Heights array.
Below you can find a Java implementation of the solution with above approach. Its time complexity is O(n^2 + n log n) & space complexity is O(n). Regarding time complexity, O(n log n) is the time taken to sort the elements using TreeMap . We have one inner loop used to populate results array which will take O(n^2) time complexity. In a future post, I will try to give a more optimized solution using tree data structure. But this solution works well & easy to understand.