Sort the People

How it works

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.

Steps

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.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Sorting in Ascending Instead of Descending Order

The problem asks for people sorted by height in descending order (tallest first). A common mistake is to sort in ascending order and forget to reverse the result or adjust the comparator.

Losing the Name-Height Association After Sorting

When sorting heights separately from names, you must maintain a way to retrieve the corresponding name for each height. Using a hash map or pairing heights with indices before sorting prevents this association from being lost.

from typing import List

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]

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = names.size();
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);

        sort(indices.begin(), indices.end(), [&](int a, int b) {
            return heights[a] > heights[b];
        });

        vector<string> res;
        for (int i : indices) {
            res.push_back(names[i]);
        }

        return res;
    }
};