Watch 10 video solutions for Sort the People, a easy level problem involving Array, Hash Table, String. This walkthrough by NeetCodeIO has 7,141 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You receive two arrays: names and heights. Each index represents a person. The task is to return the names sorted in descending order of height while keeping the correct name-height association.
This problem is essentially a sorting task with linked data. The key constraint is preserving the relationship between each name and its height while ordering by height. Most solutions rely on combining or referencing indices so the pairing is never lost during sorting.
Approach 1: Pairing and Sorting (Time: O(n log n), Space: O(n))
Create pairs that keep each person's name tied to their height. For example, combine them as (height, name) tuples or objects. Once paired, sort the list by height in descending order using a standard sorting algorithm. After sorting, iterate through the pairs and extract the names into the result array.
The key insight is that pairing eliminates the risk of losing the relationship between the two arrays during sorting. This approach is straightforward and maps directly to built‑in sort utilities available in most languages. It relies on concepts from array manipulation and sorting. Because the entire list is sorted, the complexity is dominated by the sorting step.
Approach 2: Directly Sorting Indices (Time: O(n log n), Space: O(n))
Instead of pairing values, create an index array containing 0..n-1. Sort this index array based on the values in the heights array, ordering indices so that taller heights appear first. Once sorted, iterate through the index list and pick the corresponding names from the names array.
This approach keeps the original arrays untouched and only reorders indices. The technique is common when working with parallel arrays and avoids allocating pair objects. It still performs a comparison-based sort, so the time complexity remains O(n log n). The idea frequently appears in problems involving array indexing and comparator-based sorting.
Recommended for interviews: Pairing and sorting is the most direct and readable solution, which makes it the expected answer in many interviews. Sorting indices demonstrates deeper control over memory layout and array manipulation, which can be useful when dealing with large datasets or immutable structures. Showing both approaches signals strong understanding of how to maintain relationships between multiple arrays during sorting.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pairing and Sorting | O(n log n) | O(n) | Most common and readable approach; ideal when using built-in sort with paired values. |
| Directly Sorting Indices | O(n log n) | O(n) | Useful when you want to avoid modifying the original arrays and only reorder references. |