Editorial for the Problem: Sort the People

Date: July 22, 2024

Difficulty:
Related Topics:

Editorial

The problem is to sort a list of people by their heights in descending order. Given two lists, nam (names) and h (heights), we aim to produce a sorted list of names based on their corresponding heights.

Approach

To solve this problem efficiently, we can use the following approach:

1. Pairing Names with Heights:

   • Create a vector of pairs where each pair consists of a height and the corresponding name.

2. Sorting the Pairs:

   • Sort the vector of pairs in descending order based on heights.

3. Extracting the Sorted Names:

   • Extract the names from the sorted pairs into the result vector.

Key Steps:

1. Create Pairs:

   • Pair each name with its corresponding height.

2. Sort the Pairs:

   • Sort the pairs in descending order by height using the built-in sort function.

3. Construct the Result:

   • Construct the final sorted list of names from the sorted pairs.

Code

class Solution {
public:
    vector<string> sortPeople(vector<string>& nam, vector<int>& h) {
        int n = h.size();
        vector<string> ans;
        vector<pair<int, string>> res;

        for (int i = 0; i < n; i++) {
            res.push_back({h[i], nam[i]});
        }

        sort(res.rbegin(), res.rend());

        for (auto i : res) {
            ans.push_back(i.second);
        }

        return ans;
    }
};

Explanation of Code

Pairing Names with Heights:

• A vector of pairs res is created, where each pair contains a height and the corresponding name.
• We iterate over the indices of the input lists and push the pairs into res.

Sorting the Pairs:

• The vector res is sorted in descending order by height using sort(res.rbegin(), res.rend());. This sorts the pairs based on the first element of each pair, which is the height.

Constructing the Result:

• After sorting, we iterate through the sorted pairs and extract the names, pushing them into the result vector ans.

Efficiency

The time complexity is dominated by the sorting operation, which is ( O(n log n) ), where ( n ) is the number of people. The space complexity is ( O(n) ) due to the storage of pairs and the result vector.

Like and Upvote

If you found this solution helpful, please consider liking 👍 and upvoting ⬆️. Your support helps in continuing to provide high-quality solutions.