2418. Sort the People - Explanation

Problem Link



1. Hash Map

Intuition

Since all heights are distinct, we can use each height as a unique key to look up the corresponding person's name. By building a hash map from height to name, we can then sort the heights in descending order and retrieve names in the correct sequence.

Algorithm

  1. Create a hash map that maps each height to its corresponding name.
  2. Sort the heights array in ascending order.
  3. Iterate through the sorted heights in reverse order (descending).
  4. For each height, look up the name in the hash map and add it to the res.
  5. Return the res array containing names sorted by height in descending order.
class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        height_to_name = {}
        for h, n in zip(heights, names):
            height_to_name[h] = n

        res = []
        for h in reversed(sorted(heights)):
            res.append(height_to_name[h])

        return res

Time & Space Complexity

  • Time complexity: O(nlog⁡n)O(n \log n)
  • Space complexity: O(n)O(n)

2. Sorting the Pairs

Intuition

Instead of using a hash map, we can pair each height with its corresponding name directly. By creating an array of (height, name) pairs and sorting them by height in descending order, we keep the relationship intact throughout the sorting process.

Algorithm

  1. Create an array of pairs where each pair contains (height, name).
  2. Sort the array of pairs by height in descending order.
  3. Extract the names from the sorted pairs to form the result array.
  4. Return the result.
class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        arr = list(zip(heights, names))
        arr.sort(reverse=True)
        return [name for _, name in arr]

Time & Space Complexity

  • Time complexity: O(nlog⁡n)O(n \log n)
  • Space complexity: O(n)O(n)

3. Sorting the Indices

Intuition

Rather than copying data into pairs, we can sort an array of indices based on the heights they point to. This approach is memory efficient when names are long strings, since we only move integers during sorting rather than entire strings.

Algorithm

  1. Create an array of indices from 0 to n-1.
  2. Sort the indices array using a custom comparator that compares the heights at those indices in descending order.
  3. Build the result by mapping each sorted index to its corresponding name.
  4. Return the result array.
class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        indices = list(range(len(names)))
        indices.sort(key=lambda i: -heights[i])
        return [names[i] for i in indices]

Time & Space Complexity

  • Time complexity: O(nlog⁡n)O(n \log n)
  • Space complexity: O(n)O(n)