Sort the People
Reorder names by height by sorting pairs, or by sorting indices with a custom comparator
Problem Statement
You are given an array names and an array heights, where names[i] and heights[i] describe the same person. All heights are distinct.
Return names sorted in descending order of height.
Input: names = ["Mary", "John", "Emma"]
heights = [180, 165, 170]
Output: ["Mary", "Emma", "John"]
Why: 180 > 170 > 165
Input: names = ["Alice", "Bob", "Bob"]
heights = [155, 185, 150]
Output: ["Bob", "Alice", "Bob"]Intuition
The difficulty is not the sorting — it is that the data lives in two parallel arrays. Sorting heights alone destroys the link to names: after sorting you no longer know which name went with which height.
The key insight
Keep each name glued to its height before sorting. Either:
- Zip them into pairs and sort the pairs by height, or
- Sort the indices
[0, 1, 2, …]using height as the comparison key, then read the names in that order.
Both preserve the pairing through the sort. The second uses less memory because it moves integers rather than strings.
Real-world analogy
A photo lineup. You do not sort a list of heights on paper and then guess who stands where — you ask the people themselves to arrange by height. Each person carries their name with them as they move.
Watch it run
Approach
Combine the two arrays
Zip into (height, name) pairs, or build an index array [0 … n-1].
Sort by height, descending
In Python, reverse=True. In TypeScript, a comparator of (a, b) => b - a.
Solution
def sort_people(names: list[str], heights: list[int]) -> list[str]:
"""Return names ordered from tallest to shortest."""
paired = sorted(zip(heights, names), reverse=True)
return [name for _, name in paired]The index-sorting variant, which never copies the strings:
def sort_people_by_index(names: list[str], heights: list[int]) -> list[str]:
order = sorted(range(len(names)), key=lambda i: heights[i], reverse=True)
return [names[i] for i in order]Two language-specific traps
Python: sorted(zip(heights, names)) puts heights first on purpose. Tuples compare element by element, so height is the primary key. Writing zip(names, heights) would sort alphabetically by name instead.
TypeScript: heights.sort() without a comparator sorts as strings — [9, 80, 100] becomes [100, 80, 9]. Numeric sorts always need (a, b) => a - b or its reverse.
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(n)
- Time — dominated by the sort. Building the pairs is
O(n). - Space —
O(n)for the pairs or index array plus the output. Sorting itself needsO(log n)toO(n)auxiliary space depending on the implementation.
Edge Cases
Related Problems
- H-Index — sorting to expose a property that is invisible in the original order
- Top K Frequent Elements — ordering by a derived key rather than the value itself
- Group Anagrams — sorting used as a canonical form rather than for output order