Sort the People

In this problem, we’re asked to sort an array of names in order of descending heights. The approach to solving this problem involves mapping the names to their respective heights, sorting this map by the heights, and then returning the names in the sorted order.

Here’s a Python solution using list comprehension and the built-in sorted function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from typing import List

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        # Create a map of names to heights
        name_height_map = [(names[i], heights[i]) for i in range(len(names))]

        # Sort the map in descending order by height
        sorted_map = sorted(name_height_map, key=lambda x: x[1], reverse=True)

        # Return the sorted names
        return [name for name, height in sorted_map]

This code works by first creating a list of tuples, where each tuple contains a name and its corresponding height. Then it sorts this list in descending order based on the height. Finally, it returns a new list containing only the names from the sorted list of tuples.

Beginner friendly version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

from typing import List

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        # Start by initializing an empty list to hold our tuples
        name_height_map = []

        # Next, we will fill our list with tuples, where each tuple is a pair of name and corresponding height
        for i in range(len(names)):
            name_height_map.append((names[i], heights[i]))

        # Now, we want to sort this list of tuples
        # But instead of sorting it by name (the first element of each tuple), we want to sort it by height (the second element of each tuple)
        # We use a feature of Python's sort function, where it can accept a function that it will use to decide the order of elements
        # The lambda function we're using here takes a tuple and returns the second element (the height)
        # So this will sort our list in ascending order by height
        # But we actually want it in descending order, so we add the argument reverse=True
        sorted_map = sorted(name_height_map, key=lambda x: x[1], reverse=True)

        # Now that our list is sorted, we want to return a list of the names in this order
        # We can get this by going through our sorted list and taking the first element of each tuple (the name)
        sorted_names = []
        for name, height in sorted_map:
            sorted_names.append(name)

        # Finally, we return our list of sorted names
        return sorted_names

This code accomplishes the same task as the original, but with more detailed explanations and a more verbose style that may be easier for beginners to follow.

The use of a lambda function is not strictly necessary, but it helps when we want to specify the “key” by which we should sort a collection. In this case, we want to sort a list of tuples by the second element (the height), so we use a lambda function that takes a tuple and returns the second element. This tells the sorted function to sort the tuples by their second element.

However, if you prefer not to use a lambda function, you could create a separate function that accomplishes the same task, and pass this function as the key to the sorted function.

Here’s how that might look:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from typing import List, Tuple

def get_height(person: Tuple[str, int]) -> int:
    return person[1]

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        name_height_map = []
        for i in range(len(names)):
            name_height_map.append((names[i], heights[i]))
        sorted_map = sorted(name_height_map, key=get_height, reverse=True)
        sorted_names = []
        for name, height in sorted_map:
            sorted_names.append(name)
        return sorted_names

In this version of the code, the get_height function replaces the lambda function. It takes a tuple (which we’re calling a “person” here) and returns the second element (the height). When passed as the key to sorted, it tells sorted to order the tuples by their second element, just like the lambda function did.

Identifying Problem Isomorphism

“Sort People by Height” can be approximately mapped to “Relative Sort Array”.

In “Relative Sort Array”, we’re given two lists, arr1 and arr2. We need to sort the elements of arr1 based on the order of elements in arr2. Elements of arr1 that don’t exist in arr2 should be placed at the end of arr1 in ascending order.

In “Sort People by Height”, we’re also given two lists, names and heights. We need to sort the elements of names based on the order of elements in heights. However, this problem differs in that we sort in descending order, and there is no concept of placing “extra” elements at the end of the list.

The reasoning behind this mapping is that both problems involve sorting one list based on the order of elements in another list. Although the details and constraints differ, the underlying concept is the same. This makes the problems approximately isomorphic.

“Sort People by Height” is simpler because it only involves sorting in descending order and doesn’t include the extra step of handling elements that exist in one list but not the other. “Relative Sort Array” is a more complex problem as it requires additional steps.