algoadvance

Leetcode 2418. Sort the People

Problem Statement

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 (i) ((0 \leq i < n)), (names[i]) and (heights[i]) denote the name and height of the (i)-th person.

Return the names of the people, sorted in descending order by their height.

Example:

Clarifying Questions

  1. Are the lengths of names and heights always the same?
    • Yes, both arrays will always have the same length n.
  2. Can the names array have duplicate names?
    • No, the problem does not specify uniqueness in names but specifies that heights are distinct.
  3. What is the range of n?
    • Typical constraints would be useful, but generally, you can assume (1 \leq n \leq 10^4).

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
    // Create a vector of pairs (height, name)
    vector<pair<int, string>> people;
    for (int i = 0; i < names.size(); ++i) {
        people.emplace_back(heights[i], names[i]);
    }

    // Sort the people by height in descending order
    sort(people.begin(), people.end(), [](const pair<int, string>& a, const pair<int, string>& b) {
        return b.first < a.first; // Sort in descending order
    });

    // Extract the sorted names
    vector<string> sortedNames;
    for (const auto& person : people) {
        sortedNames.push_back(person.second);
    }

    return sortedNames;
}

// Example usage
int main() {
    vector<string> names = {"Mary", "John", "Emma"};
    vector<int> heights = {180, 165, 170};
    vector<string> sortedNames = sortPeople(names, heights);

    for (const string& name : sortedNames) {
        cout << name << " ";
    }
    cout << endl;

    // Expected Output: Mary Emma John

    return 0;
}

Strategy

  1. Combine into Pairs: Pair each name with its corresponding height. This will help to sort them together.
  2. Sort the Pairs: Use the sort function with a custom comparator to sort the pairs based on heights in descending order.
  3. Extract Names: Once sorted, extract names from the pairs in the new order.

Using this strategy, you can ensure that the names are sorted by height efficiently.

Time Complexity

Therefore, the overall time complexity is (O(n \log n)). The space complexity is (O(n)) due to the additional storage needed for the pair vector.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI