Repository files navigation

Difficulty:
Related Topics:

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

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.

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.

classSolution {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;    }};

Pairing Names with Heights:

• A vector of pairsres 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 intores.

Sorting the Pairs:

• The vectorres is sorted in descending order by height usingsort(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 vectorans.

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.

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