#2418

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Sort the People

Sort the People requires pairing names with heights and sorting them in descending height order efficiently using arrays and hash lookups.

array hash table string sorting

Problem Statement

Given two arrays of equal length, names and heights, where names[i] is a string representing the name of the ith person and heights[i] is a distinct positive integer representing that person's height, return an array of names sorted from tallest to shortest. The arrays are guaranteed to have the same length n and each height is unique.

You must maintain the correct name-to-height mapping when sorting. For example, if the tallest person is at index 2, their name should appear first in the output. This requires scanning through the arrays and performing swaps or mapping lookups to reorder names efficiently according to the descending heights.

Examples

Example 1

Input: names = ["Mary","John","Emma"], heights = [180,165,170]

Output: ["Mary","Emma","John"]

Mary is the tallest, followed by Emma and John.

Example 2

Input: names = ["Alice","Bob","Bob"], heights = [155,185,150]

Output: ["Bob","Alice","Bob"]

The first Bob is the tallest, followed by Alice and the second Bob.

Constraints

n == names.length == heights.length
1 <= n <= 103
1 <= names[i].length <= 20
1 <= heights[i] <= 105
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

Solution Approach

Pair Names with Heights

Create an array of tuples where each tuple contains a height and its corresponding name. This ensures that the mapping between names and heights remains intact during sorting.

Sort by Height Descending

Use the built-in sort function or any comparison-based sort on the array of tuples, sorting by the height value in descending order. This leverages the array scanning plus hash lookup pattern to correctly order names.

Extract Sorted Names

After sorting, iterate through the array of tuples and collect the names in order. This step returns the final array of names sorted from tallest to shortest while preserving their original associations.

Complexity Analysis

Metric	Value
Time	O(n \cdot \log n)
Space	O(n)

Time complexity is O(n \cdot \log n) due to the sorting of n elements. Space complexity is O(n) because we create an auxiliary array of tuples pairing names and heights.

What Interviewers Usually Probe

Expect a direct mapping of names to heights and correct descending sort order.
Be prepared to explain why a hash or tuple-based approach avoids mixing names and heights.
Highlight the pattern of scanning arrays and using auxiliary structures for sorting without losing associations.

Common Pitfalls or Variants

Common pitfalls

Sorting names and heights separately without pairing can misalign names with heights.
Assuming heights are not distinct and trying to handle duplicates unnecessarily.
Forgetting to return only names in the final output instead of height-name pairs.

Follow-up variants

Sort by other attributes such as weight or age while keeping name mapping intact.
Handle duplicate heights by breaking ties alphabetically or by original index.
Sort names in ascending height order instead of descending.

FAQ

What is the most efficient way to solve Sort the People?

Pair each name with its height, sort the pairs by height descending using array scanning and hash lookup, then extract names.

Can I sort names and heights separately?

No, sorting separately breaks the association between names and heights, leading to incorrect output.

Does this problem work with duplicate heights?

The original constraints guarantee distinct heights, so handling duplicates is unnecessary unless the variant specifies it.

What data structure ensures name-height mapping is preserved during sort?

Using tuples or pairs of (height, name) maintains the mapping and allows safe sorting by height.

How does array scanning plus hash lookup help in Sort the People?

It allows finding the tallest remaining person efficiently at each step and swapping or reordering names without losing associations.

terminal

Solution

Solution 1: Sorting

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

1

2

3

4

5

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]

Solution 2

#### Python3

1

2

3

4

5

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]

Continue Practicing