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.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.
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.
Java
C++
C
C#
JavaScript
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(n) for storing the list of 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.
The code sorts indices based on the heights using negative heights to direct the sorting to descending order. After sorting, use these indices to create the sorted list of names.
Java
C++
C
C#
JavaScript
Time Complexity: O(n log n) due to sorting the indices.
Space Complexity: O(n) for auxiliary storage of indices.
| Approach | Complexity |
|---|---|
| Approach 1: Pairing and Sorting | Time Complexity: O(n log n) due to the sorting operation. |
| Approach 2: Directly Sorting Indices | Time Complexity: O(n log n) due to sorting the indices. |
Sort the People - Leetcode 2418 - Python • NeetCodeIO • 6,435 views views
Watch 9 more video solutions →Practice Sort the People with our built-in code editor and test cases.
Practice on FleetCode