You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.
For each index i, names[i] and heights[i] denote the name and height of the ith person.
Return names sorted in descending order by the people's heights.
Example 1:
Input: names = ["Mary","John","Emma"], heights = [180,165,170] Output: ["Mary","Emma","John"] Explanation: Mary is the tallest, followed by Emma and John.
Example 2:
Input: names = ["Alice","Bob","Bob"], heights = [155,185,150] Output: ["Bob","Alice","Bob"] Explanation: The first Bob is the tallest, followed by Alice and the second Bob.
Constraints:
n == names.length == heights.length1 <= n <= 1031 <= names[i].length <= 201 <= heights[i] <= 105names[i] consists of lower and upper case English letters.heights are distinct.The key idea in #2418 Sort the People is to order people's names based on their corresponding heights in descending order. Since the heights array determines the ranking, a common strategy is to pair each name with its height and then apply a sorting algorithm based on the height value.
One intuitive approach is to create a list of pairs like (height, name) and sort the list in descending order of height. After sorting, extract the names in that order to produce the final result. Another efficient technique is to sort the indices of the heights array instead of modifying the original arrays. This keeps the data structure simple and avoids extra pair creation.
Because sorting dominates the process, the overall time complexity is typically O(n log n), while the additional space depends on the chosen structure for storing pairs or indices. This approach is straightforward and commonly used in interview settings when ordering elements based on related values.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Pair names with heights and sort | O(n log n) | O(n) |
| Sort indices based on heights | O(n log n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Find the tallest person and swap with the first person, then find the second tallest person and swap with the second person, etc. Repeat until you fix all n people.
This approach involves pairing each name with its corresponding height, sorting these pairs by height in descending order, and then extracting the sorted names. This makes use of the association between each name and its corresponding height.
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(n) for storing the list of tuples.
1def sort_people(names, heights):
2 paired_list = list(zip(heights, names))
3 paired_list.sort(reverse=True, key=lambda x: x[The code creates a list of tuples, each containing a height and the corresponding name. The list is then sorted in descending order based on the height, by using a lambda function as the sorting key. Finally, the sorted names are extracted from the tuples.
Rather than pairing names and heights, you can directly sort the indices of the height array. After sorting the indices by descending heights, you can retrieve the names based on this sorted order of heights.
Time Complexity: O(n log n) due to sorting the indices.
Space Complexity: O(n) for auxiliary storage of indices.
1import
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
While this exact problem may not always appear, similar sorting and mapping problems are very common in FAANG-style interviews. Understanding how to sort related arrays or pair values with keys is a frequently tested skill.
The optimal approach is to pair each person's height with their name and sort the pairs in descending order of height. After sorting, extract the names in order. This method is simple and runs in O(n log n) time due to sorting.
Arrays or lists combined with pairs or indices work best for this problem. You can store (height, name) pairs or sort indices based on the heights array. Both structures allow efficient sorting and easy reconstruction of the result.
Yes, you can sort an array of indices based on the values in the heights array. After sorting the indices in descending order of height, map them back to the names array to produce the sorted list.
Indices of arrays are sorted based on the heights they correspond to using a comparator for descending order. Then the sorted indices are used to grab the right names.