2418. Sort the People

Problem

Question

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.

For each index i, names[i] and heights[i] denote the name and height of the ith person.

Return names sorted in descending order by the people’s heights.

Example 1:

Input: names = [“Mary”,“John”,“Emma”], heights = [180,165,170] Output: [“Mary”,“Emma”,“John”] Explanation: Mary is the tallest, followed by Emma and John.

Example 2:

Input: names = [“Alice”,“Bob”,“Bob”], heights = [155,185,150] Output: [“Bob”,“Alice”,“Bob”] Explanation: 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.

---

Solutions

1. Zip & Sort

Time Complexity: $O(n\log n)$ | Space Complexity: $O(n)$

The easiest approach in python written in a minute.

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

---

2.🍔 Zip & Sort One-liner

Time Complexity: $O(n\log n)$ | Space Complexity: $O(n)$

The same approach, but in one liner. Note: .sort function returns None. Therefore, we need to use function sorted.

def get_sorted_names(heights, names):
    return [person[1] for person in sorted(zip(heights, names), reverse=True)]

---

3. Bubble Sort

Time Complexity: $O(n^2)$ | Space Complexity: $O(1)$

The idea behind Bubble Sort is simple: compare two adjacent elements and swap them if needed. Note: the inner loop can end at len(heights) - i - 1 since the largest unsorted element will always ‘bubble up’ to the end.”

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
 
        for i in range(0, len(heights)):
            for j in range(0, len(heights) - i - 1):
                if heights[j] < heights[j + 1]:
                    heights[j + 1], heights[j] = heights[j], heights[j + 1]
                    names[j + 1], names[j] = names[j], names[j + 1]
            
        return names
 

---

4. Selection Sort

Time Complexity: $O(n^2)$ | Space Complexity: $O(1)$

Another simple sorting algorithm is Selection Sort. We find the maximum element, place it at the start, and then continue from the next position.

Interesting fact: While the time and space complexities are the same, selection sort can be a better algorithm than bubble sort if the cost of writing to memory matters. In this algorithm, we make O(n)O(n) swaps, not O(n2)O(n2).

from typing import List
 
class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        
        for i in range(0, len(heights) - 1):
            max_index = i
            for j in range(i + 1, len(heights)):
                if heights[max_index] < heights[j]:
                    max_index = j
            heights[i], heights[max_index] = heights[max_index], heights[i]
            names[i], names[max_index] = names[max_index], names[i]           
 
        return names

---

5. Insertion Sort

Time Complexity: $O(n^2)$ | Space Complexity: $O(1)$

The name speaks for itself. We simulate the insertion of the items into their correct place. First, we assume that the first item is in the right spot. We pick the next value and iterate backward until we find its place, swapping the values as we go.

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        
        for i in range(1, len(heights)):
            key = heights[i]
            key_name = names[i]
            j = i - 1
 
            while j >= 0 and key > heights[j]:
                heights[j + 1] = heights[j]
                names[j + 1] = names[j]
                j -= 1
            
            heights[j + 1] = key
            names[j + 1] = key_name
 
        return names
 

---