# 2418. Sort the People

## Description

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.length
• 1 <= n <= 103
• 1 <= names[i].length <= 20
• 1 <= heights[i] <= 105
• names[i] consists of lower and upper case English letters.
• All the values of heights are distinct.

## Solutions

Solution 1: Sorting

According to the problem description, we can create an index array $idx$ of length $n$, where $idx[i]=i$. Then we sort each index in $idx$ in descending order according to the corresponding height in $heights$. Finally, we traverse each index $i$ in the sorted $idx$ and add $names[i]$ to the answer array.

We can also create an array $arr$ of length $n$, where each element is a tuple $(heights[i], i)$. Then we sort $arr$ in descending order by height. Finally, we traverse each element $(heights[i], i)$ in the sorted $arr$ and add $names[i]$ to the answer array.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the arrays $names$ and $heights$.

• class Solution {
public String[] sortPeople(String[] names, int[] heights) {
int n = names.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; ++i) {
idx[i] = i;
}
Arrays.sort(idx, (i, j) -> heights[j] - heights[i]);
String[] ans = new String[n];
for (int i = 0; i < n; ++i) {
ans[i] = names[idx[i]];
}
return ans;
}
}

• class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
int n = names.size();
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j) { return heights[j] < heights[i]; });
vector<string> ans;
for (int i : idx) {
ans.push_back(names[i]);
}
return ans;
}
};

• class Solution:
def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
idx = list(range(len(heights)))
idx.sort(key=lambda i: -heights[i])
return [names[i] for i in idx]


• func sortPeople(names []string, heights []int) (ans []string) {
n := len(names)
idx := make([]int, n)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool { return heights[idx[j]] < heights[idx[i]] })
for _, i := range idx {
ans = append(ans, names[i])
}
return
}

• function sortPeople(names: string[], heights: number[]): string[] {
const n = names.length;
const idx = new Array(n);
for (let i = 0; i < n; ++i) {
idx[i] = i;
}
idx.sort((i, j) => heights[j] - heights[i]);
const ans: string[] = [];
for (const i of idx) {
ans.push(names[i]);
}
return ans;
}


• impl Solution {
pub fn sort_people(names: Vec<String>, heights: Vec<i32>) -> Vec<String> {
let mut combine: Vec<(String, i32)> = names.into_iter().zip(heights.into_iter()).collect();
combine.sort_by(|a, b| b.1.cmp(&a.1));
combine
.iter()
.map(|s| s.0.clone())
.collect()
}
}