Difficulty: Easy | Acceptance: 84.80% | Paid: No Topics: Array, Hash Table, String, Sorting
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.
- Examples
- Constraints
- Pair and Sort
- Index Array Sort
- Bucket Sort
- TreeMap Approach
Examples
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.length
- 1 <= n <= 10^3
- 1 <= names[i].length <= 20
- 1 <= heights[i] <= 10^5
- names[i] consists of lower and upper case English letters.
- All the values of heights are distinct.
Pair and Sort
Intuition Create pairs of (height, name) and sort them by height in descending order, then extract the names.
Steps
- Create a list of pairs where each pair contains (height, name).
- Sort the list in descending order by height.
- Extract names from the sorted pairs.
class Solution:
def sortPeople(self, names: list[str], heights: list[int]) -> list[str]:
people = list(zip(heights, names))
people.sort(reverse=True)
return [name for _, name in people]
Complexity
- Time: O(n log n)
- Space: O(n)
- Notes: Simple and straightforward approach using built-in sorting.
Index Array Sort
Intuition Create an array of indices and sort them based on heights in descending order, then use these sorted indices to get the names.
Steps
- Create an array of indices [0, 1, 2, …, n-1].
- Sort the indices based on heights in descending order.
- Use the sorted indices to build the result array of names.
class Solution:
def sortPeople(self, names: list[str], heights: list[int]) -> list[str]:
indices = list(range(len(names)))
indices.sort(key=lambda i: heights[i], reverse=True)
return [names[i] for i in indices]
Complexity
- Time: O(n log n)
- Space: O(n)
- Notes: Avoids creating additional pair objects, only uses indices.
Bucket Sort
Intuition Since heights have a limited range (1 to 10⁵), use bucket sort by creating an array where index represents height.
Steps
- Find the maximum height.
- Create a bucket array where each index represents a height.
- Place each name at its corresponding height index.
- Iterate from max height to 1 and collect names.
class Solution:
def sortPeople(self, names: list[str], heights: list[int]) -> list[str]:
max_height = max(heights)
bucket = [[] for _ in range(max_height + 1)]
for name, height in zip(names, heights):
bucket[height].append(name)
result = []
for h in range(max_height, 0, -1):
result.extend(bucket[h])
return result
Complexity
- Time: O(n + max_height)
- Space: O(n + max_height)
- Notes: Linear time complexity but uses more space when max_height is large.
TreeMap Approach
Intuition Use a TreeMap (or equivalent) to map heights to names, then iterate in descending order of keys.
Steps
- Create a map from height to name.
- Iterate through the map in descending order of keys (heights).
- Collect names in order.
class Solution:
def sortPeople(self, names: list[str], heights: list[int]) -> list[str]:
height_to_name = {}
for name, height in zip(names, heights):
height_to_name[height] = name
sorted_heights = sorted(height_to_name.keys(), reverse=True)
return [height_to_name[h] for h in sorted_heights]
Complexity
- Time: O(n log n)
- Space: O(n)
- Notes: Uses tree-based data structure for automatic sorting by keys.