Problem Description

You have two arrays of the same length n:

• names: an array of strings representing people's names
• heights: an array of distinct positive integers representing the corresponding heights

Each person at index i has name names[i] and height heights[i].

Your task is to return the names array sorted in descending order based on the people's heights. In other words, you need to rearrange the names so that the person with the tallest height comes first, followed by the second tallest, and so on.

For example, if you have:

• names = ["Alice", "Bob", "Charlie"]
• heights = [155, 185, 170]

The output should be ["Bob", "Charlie", "Alice"] because:

• Bob has height 185 (tallest)
• Charlie has height 170 (second tallest)
• Alice has height 155 (shortest)

Since all heights are distinct (no two people have the same height), there will be a unique ordering of names in the result.

Intuition

The core challenge here is that we need to sort one array (names) based on the values in another array (heights). We can't simply sort the heights array alone because we'd lose the connection between each person's name and their height.

Think of it like having a list of students with their test scores. If we just sort the scores, we wouldn't know which score belongs to which student anymore. We need to maintain the relationship between the two pieces of information.

The key insight is to use indices as a bridge between the two arrays. Since names[i] and heights[i] correspond to the same person, we can:

1. Create an index array [0, 1, 2, ..., n-1]
2. Sort these indices based on the heights they point to
3. Use the sorted indices to reconstruct the names in the correct order

For example, if we have heights [155, 185, 170] with indices [0, 1, 2]:

• Index 1 points to height 185 (largest)
• Index 2 points to height 170 (middle)
• Index 0 points to height 155 (smallest)

So our sorted indices would be [1, 2, 0], and we can use these to pick names in order: names[1], names[2], names[0].

This approach elegantly solves the problem of sorting paired data - we sort the "keys" (indices) based on one criterion (heights) while maintaining the ability to retrieve the associated values (names).

Learn more about Sorting patterns.

Solution Approach

The solution implements the index-based sorting strategy we identified. Let's walk through the implementation step by step:

Step 1: Create an index array

idx = list(range(len(heights)))

This creates a list idx = [0, 1, 2, ..., n-1] where each element represents an index position. These indices will serve as pointers to both the names and heights arrays.

Step 2: Sort indices by height in descending order

idx.sort(key=lambda i: -heights[i])

This is the crucial step. We sort the idx array, but not by the index values themselves. Instead, we use a custom sorting key: lambda i: -heights[i].

• For each index i in idx, we look up heights[i]
• The negative sign -heights[i] ensures descending order (Python's sort is ascending by default)
• After sorting, idx[0] will contain the index of the person with the maximum height, idx[1] will have the index of the second tallest person, and so on

Step 3: Build the result using sorted indices

return [names[i] for i in idx]

This list comprehension iterates through the sorted indices and constructs a new list by picking names in the order specified by the sorted indices.

Example walkthrough:

• Input: names = ["Alice", "Bob", "Charlie"], heights = [155, 185, 170]
• Initial idx = [0, 1, 2]
• After sorting by -heights[i]: idx = [1, 2, 0] (because heights[1]=185 is largest, heights[2]=170 is second, heights[0]=155 is smallest)
• Final result: [names[1], names[2], names[0]] = ["Bob", "Charlie", "Alice"]

Alternative approach mentioned: Instead of sorting indices, we could create tuples of (height, index) pairs, sort these tuples by height in descending order, and then extract the names using the indices from the sorted tuples. Both approaches achieve the same result with O(n log n) time complexity due to sorting.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• names = ["Mary", "John", "Emma"]
• heights = [180, 165, 158]

Goal: Return names sorted by height in descending order.

Step 1: Create index array

idx = [0, 1, 2]

Each index corresponds to a person:

• Index 0 → Mary (height 180)
• Index 1 → John (height 165)
• Index 2 → Emma (height 158)

Step 2: Sort indices by height (descending) For each index, we evaluate -heights[i]:

• Index 0: -heights[0] = -180
• Index 1: -heights[1] = -165
• Index 2: -heights[2] = -158

Sorting by these values (smallest to largest):

• -180 comes first (most negative)
• -165 comes second
• -158 comes third (least negative)

So idx remains [0, 1, 2] after sorting.

Step 3: Build result using sorted indices

result = [names[0], names[1], names[2]]
       = ["Mary", "John", "Emma"]

The final output is ["Mary", "John", "Emma"] - correctly ordered from tallest to shortest!

Another example with mixed ordering:

• names = ["Sam", "Pat", "Alex"]
• heights = [170, 190, 160]

1. idx = [0, 1, 2]
2. Sort by -heights[i]:
   • Index 0: -170 (middle)
   • Index 1: -190 (smallest/first)
   • Index 2: -160 (largest/last)
   • Sorted idx = [1, 0, 2]
3. Build result: [names[1], names[0], names[2]] = ["Pat", "Sam", "Alex"]

This demonstrates how the index sorting preserves the name-height relationship while achieving the desired ordering.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The dominant operation in this code is the sorting step idx.sort(key=lambda i: -heights[i]), which sorts the indices based on the heights in descending order. The time complexity of Python's built-in sort (Timsort) is O(n × log n) where n is the number of elements being sorted. Creating the initial index list with list(range(len(heights))) takes O(n) time, and the list comprehension [names[i] for i in idx] also takes O(n) time. Since O(n × log n) dominates O(n), the overall time complexity is O(n × log n).

Space Complexity: O(n)

The code creates an additional list idx of size n to store the indices, which requires O(n) space. The final list comprehension creates a new list of names with n elements, also requiring O(n) space. The sorting algorithm itself may use additional space (Python's Timsort uses up to O(n) auxiliary space in the worst case). Therefore, the total space complexity is O(n), where n is the length of the input arrays names and heights.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Arrays

A common mistake is trying to sort the heights array directly and then attempting to track which names correspond to which heights:

Incorrect approach:

def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
    heights.sort(reverse=True)  # This loses the connection to names!
    # Now we can't determine which name belongs to which height

Why it fails: Once you sort heights independently, you lose the positional relationship between names and heights. The original pairing is destroyed.

Solution: Always maintain the relationship between paired data by either:

• Sorting indices (as shown in the solution)
• Creating tuples that keep the data together

2. Using the Wrong Sorting Order

Forgetting to sort in descending order or incorrectly implementing it:

Incorrect approaches:

# Mistake 1: Forgetting descending order
indices.sort(key=lambda i: heights[i])  # This sorts ascending!

# Mistake 2: Using reverse incorrectly
indices.sort(key=lambda i: heights[i], reverse=True)  # This works but less elegant

Solution: Use the negative sign trick (-heights[i]) or explicitly use reverse=True parameter in the sort function.

3. Creating Unnecessary Data Structures

Some might overcomplicate by creating dictionaries or complex objects:

Overcomplicated approach:

def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
    # Unnecessary dictionary creation
    height_to_name = {heights[i]: names[i] for i in range(len(heights))}
    sorted_heights = sorted(heights, reverse=True)
    return [height_to_name[h] for h in sorted_heights]

Why it's problematic: While this works for distinct heights, it:

• Uses extra space unnecessarily (O(n) for the dictionary)
• Would fail if heights weren't distinct (though the problem guarantees they are)
• Is more complex than needed

Solution: Stick to index-based sorting or tuple pairing for cleaner, more efficient code.

4. Inefficient Zip and Unzip Pattern

While using zip is valid, be careful with the unpacking:

Potentially confusing approach:

def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
    paired = sorted(zip(heights, names), reverse=True)
    return [name for _, name in paired]  # Easy to mix up the order

Common mistake: Forgetting which element comes first in the tuple or unpacking in the wrong order.

Solution: If using zip, be explicit about the order and consider adding comments to clarify which element is which in the tuple.