2418. Sort the People

SourceWeekly Contest 312 Q1DifficultyEasyRating1193

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 i^th 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 <= 10³
1 <= names[i].length <= 20
1 <= heights[i] <= 10⁵
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

Solutions

Solution 1: Sorting

Thinking

With \(n\le 10^3\), sort names by descending height. Heights are unique, so the key is total. Sort indices by \(\textit{heights}\) descending, then emit \(\textit{names}[i]\).

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

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

The time complexity is \(O(n \log n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the arrays \(\textit{names}\) and \(\textit{heights}\).

Python3JavaC++GoTypeScriptRust

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]

class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Integer[] idx = new Integer[n];
        Arrays.setAll(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;
    }
};

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()
    }
}

Solution 2

Thinking

Method 1 already sorts via an index array. Zipping height with name and sorting that pair descending removes the extra index array; the order is the same.

Python3JavaC++GoTypeScript

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        return [name for _, name in sorted(zip(heights, names), reverse=True)]

class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; ++i) {
            arr[i] = new int[] {heights[i], i};
        }
        Arrays.sort(arr, (a, b) -> b[0] - a[0]);
        String[] ans = new String[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = names[arr[i][1]];
        }
        return ans;
    }
}

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = names.size();
        vector<pair<int, int>> arr;
        for (int i = 0; i < n; ++i) {
            arr.emplace_back(-heights[i], i);
        }
        sort(arr.begin(), arr.end());
        vector<string> ans;
        for (int i = 0; i < n; ++i) {
            ans.emplace_back(names[arr[i].second]);
        }
        return ans;
    }
};

func sortPeople(names []string, heights []int) []string {
    n := len(names)
    arr := make([][2]int, n)
    for i, h := range heights {
        arr[i] = [2]int{h, i}
    }
    sort.Slice(arr, func(i, j int) bool { return arr[i][0] > arr[j][0] })
    ans := make([]string, n)
    for i, x := range arr {
        ans[i] = names[x[1]]
    }
    return ans
}

function sortPeople(names: string[], heights: number[]): string[] {
    return names
        .map<[string, number]>((s, i) => [s, heights[i]])
        .sort((a, b) => b[1] - a[1])
        .map(([v]) => v);
}