```
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.

import java.util.*; import java.lang.*; import java.io.*; class Solution { public ArrayList<Integer> order(ArrayList<Integer> A, ArrayList<Integer> B) { ArrayList<Integer> results = new ArrayList<Integer>(); for(int i=0; i<A.size(); i++){ results.add(-1); } //using TreeMap to sort the key by ascending order TreeMap<Integer, Integer> sortedHeights = new TreeMap<Integer, Integer>(); for(int i=0; i<A.size(); i++){ sortedHeights.put(A.get(i), B.get(i)); } for(int height : sortedHeights.keySet()){ int inFront = sortedHeights.get(height); int pos = 0; int i = 0; while(inFront > pos || results.get(i) != -1){ if(results.get(i) == -1 || results.get(i) > height){ pos++; } i++; } results.set(i, height); } return results; } }

## No comments:

## Post a Comment