LeetCode Problem 2418

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String, Sorting

Solution

LeetCode 2418, Sort the People

Problem Understanding

This problem gives us two arrays of equal length:

• names[i] represents the name of a person
• heights[i] represents the height of that same person

The two arrays are aligned by index, meaning the person at index i has both the name names[i] and the height heights[i].

The goal is to return the names array sorted in descending order according to the corresponding heights. In other words, the tallest person should appear first, the second tallest next, and so on.

For example:

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

Mary has height 180, John has height 165, and Emma has height 170.

Sorting by height in descending order gives:

180 -> Mary
170 -> Emma
165 -> John

So the final result becomes:

["Mary","Emma","John"]

The constraints are small:

• n <= 1000
• Heights are distinct
• Heights are positive integers

The most important guarantee is that all heights are distinct. This means there are no ties when sorting, which simplifies the logic because every person has a unique position in the sorted order.

Some edge cases worth considering include:

• A single person in the input
• Already sorted heights
• Reverse sorted heights
• Duplicate names with different heights
• Very small or very large height values within constraints

A naive implementation could accidentally lose the relationship between names and heights while sorting. The key challenge is preserving that mapping correctly.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly find the tallest remaining person and append their name to the result.

The algorithm would work like this:

1. Scan the heights array to find the maximum height.
2. Add the corresponding name to the answer.
3. Remove or mark that person as processed.
4. Repeat until all people are processed.

This works because each iteration selects the next tallest unprocessed person. However, every selection requires scanning the remaining array again.

If there are n people:

• First scan costs O(n)
• Second scan costs O(n - 1)
• Third scan costs O(n - 2)

This results in a total time complexity of O(n²).

Although n <= 1000 is small enough for this to pass, it is not the most efficient or elegant solution.

Optimal Approach

The better solution is to sort the people directly by height.

The key insight is that we should keep each person's name and height together while sorting. Instead of sorting heights independently, we combine the related data into pairs:

(height, name)

Then we sort these pairs in descending order by height.

Because modern sorting algorithms are highly optimized, this approach runs in O(n log n) time.

The heights are guaranteed to be distinct, so the ordering is always unambiguous.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) or O(n)	Repeatedly scans for the tallest remaining person
Optimal	O(n log n)	O(n)	Sorts paired height-name data directly

Algorithm Walkthrough

Optimal Sorting Algorithm

1. Create pairs of heights and names.

We combine the two arrays so that each person's data stays connected during sorting.

Example:

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

becomes:

[(180, "Mary"), (170, "Emma"), (165, "John")]

2. Sort the pairs in descending order by height.

Since the problem asks for tallest to shortest, we sort using the height value in reverse order.

After sorting:

[(180, "Mary"), (170, "Emma"), (165, "John")]

If the input were unsorted, sorting would rearrange the pairs correctly. 3. Extract the names from the sorted pairs.

Once the people are ordered correctly by height, we only need the names for the final answer.

Example:

["Mary", "Emma", "John"]

4. Return the resulting list.

Why it works

The algorithm works because sorting rearranges entire (height, name) pairs together. This preserves the relationship between each person and their height. Since sorting is performed by height in descending order, the resulting order of names exactly matches the required tallest-to-shortest arrangement.

Python Solution

from typing import List

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        people = list(zip(heights, names))

        people.sort(reverse=True)

        sorted_names = [name for _, name in people]

        return sorted_names

The implementation starts by using zip() to combine heights and names into pairs. Each pair contains a height and its corresponding name.

people = list(zip(heights, names))

This ensures the relationship between a person and their height remains intact during sorting.

Next, the list is sorted in descending order:

people.sort(reverse=True)

Since the height is the first element of each tuple, Python automatically sorts by height first.

After sorting, a list comprehension extracts only the names:

sorted_names = [name for _, name in people]

Finally, the sorted list of names is returned.

Go Solution

package main

import "sort"

func sortPeople(names []string, heights []int) []string {
	type Person struct {
		name   string
		height int
	}

	people := make([]Person, len(names))

	for i := 0; i < len(names); i++ {
		people[i] = Person{
			name:   names[i],
			height: heights[i],
		}
	}

	sort.Slice(people, func(i, j int) bool {
		return people[i].height > people[j].height
	})

	result := make([]string, len(names))

	for i := 0; i < len(people); i++ {
		result[i] = people[i].name
	}

	return result
}

The Go solution follows the same overall logic as the Python version, but Go requires a custom struct to store related data.

A Person struct keeps each name associated with its height:

type Person struct {
    name   string
    height int
}

The solution uses sort.Slice with a custom comparison function to sort by descending height.

Unlike Python, Go does not have built-in tuple sorting, so the comparison logic must be written explicitly.

Go slices naturally handle empty and non-empty cases correctly, so no special handling is required.

Worked Examples

Example 1

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

Step 1, Create Pairs

Height	Name
180	Mary
165	John
170	Emma

Internal representation:

[(180, "Mary"), (165, "John"), (170, "Emma")]

Step 2, Sort Descending by Height

Sorted pairs:

[(180, "Mary"), (170, "Emma"), (165, "John")]

Position	Height	Name
0	180	Mary
1	170	Emma
2	165	John

Step 3, Extract Names

["Mary", "Emma", "John"]

Final output:

["Mary","Emma","John"]

Example 2

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

Step 1, Create Pairs

Height	Name
155	Alice
185	Bob
150	Bob

Internal representation:

[(155, "Alice"), (185, "Bob"), (150, "Bob")]

Step 2, Sort Descending by Height

Sorted pairs:

[(185, "Bob"), (155, "Alice"), (150, "Bob")]

Position	Height	Name
0	185	Bob
1	155	Alice
2	150	Bob

Step 3, Extract Names

["Bob", "Alice", "Bob"]

Final output:

["Bob","Alice","Bob"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Extra storage is used for paired data

The algorithm spends most of its time sorting the list of people. Comparison-based sorting algorithms require O(n log n) time in the average and worst cases.

Additional space is required to store the combined (height, name) pairs and the output array.

Test Cases

from typing import List

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        people = list(zip(heights, names))
        people.sort(reverse=True)
        return [name for _, name in people]

solution = Solution()

# Provided example 1
assert solution.sortPeople(
    ["Mary", "John", "Emma"],
    [180, 165, 170]
) == ["Mary", "Emma", "John"]

# Provided example 2
assert solution.sortPeople(
    ["Alice", "Bob", "Bob"],
    [155, 185, 150]
) == ["Bob", "Alice", "Bob"]

# Single person
assert solution.sortPeople(
    ["Alex"],
    [190]
) == ["Alex"]

# Already sorted descending
assert solution.sortPeople(
    ["A", "B", "C"],
    [300, 200, 100]
) == ["A", "B", "C"]

# Reverse sorted input
assert solution.sortPeople(
    ["A", "B", "C"],
    [100, 200, 300]
) == ["C", "B", "A"]

# Random ordering
assert solution.sortPeople(
    ["Tom", "Jerry", "Spike"],
    [170, 180, 160]
) == ["Jerry", "Tom", "Spike"]

# Minimum and maximum heights
assert solution.sortPeople(
    ["Low", "High"],
    [1, 100000]
) == ["High", "Low"]

# Duplicate names with different heights
assert solution.sortPeople(
    ["Sam", "Sam", "Sam"],
    [150, 170, 160]
) == ["Sam", "Sam", "Sam"]

Test Case Summary

Test	Why
Example 1	Validates standard sorting behavior
Example 2	Confirms duplicate names are handled correctly
Single person	Tests minimum input size
Already sorted descending	Ensures no unnecessary reordering
Reverse sorted input	Verifies full sorting behavior
Random ordering	Tests general correctness
Minimum and maximum heights	Confirms extreme constraint values work
Duplicate names with different heights	Ensures names are not assumed unique

Edge Cases

Single Element Input

If there is only one person, the algorithm should simply return that person's name unchanged.

A buggy implementation might accidentally assume multiple elements exist when sorting or indexing. This implementation handles the case naturally because sorting a single-element list is valid and produces the same list.

Duplicate Names

The problem does not guarantee unique names. Two or more people may share the same name while having different heights.

A flawed solution using a dictionary keyed by name could overwrite entries and lose information. This implementation avoids that issue by storing complete (height, name) pairs rather than mapping names uniquely.

Already Sorted or Reverse Sorted Inputs

Some sorting implementations behave incorrectly when assumptions are made about initial ordering.

For example:

heights = [300, 200, 100]

is already correctly ordered, while:

heights = [100, 200, 300]

requires complete reversal.

The implementation relies entirely on the sorting algorithm rather than trying to optimize based on current order, so both cases are handled correctly.

Extreme Height Values

The constraints allow heights as small as 1 and as large as 100000.

A solution that performs arithmetic transformations unnecessarily could risk overflow in some languages. This implementation only compares integers directly, so it safely handles the full range of valid height values.