Leetcode 2418: Sort the People

Input: You are given two arrays: one for the names and one for the heights of n people.

Example: names = ["Tom", "Jerry", "Mickey"], heights = [170, 160, 175]

Constraints:

• 1 <= n <= 1000

• 1 <= names[i].length <= 20

• 1 <= heights[i] <= 10^5

• names[i] consists of lower and upper case English letters.

• All heights are distinct.

Output: Return the names of the people sorted in descending order by height.

Example: Output: ["Mickey", "Tom", "Jerry"]

Constraints:

Goal: Sort the people by their heights in descending order while maintaining the correct mapping of names.

Steps:

• 1. Create a list of pairs, each containing a height and a corresponding name.

• 2. Sort the pairs in descending order by height.

• 3. Extract and return the sorted names.

Goal: The solution should handle sorting and efficiently process up to 1000 names and heights.

Steps:

• The number of people (n) is at most 1000.

• The heights array contains distinct values.

Assumptions:

• The names array contains distinct names and corresponds to the heights array.

• Input: Input: names = ["Tom", "Jerry", "Mickey"], heights = [170, 160, 175]

• Explanation: The heights are sorted as [175, 170, 160], so the corresponding names are sorted as ["Mickey", "Tom", "Jerry"].

Approach: We can solve this problem by creating a list of pairs and sorting them based on the heights in descending order.

Observations:

• We need to sort the names based on their corresponding heights.

• Since the heights are distinct, we don't need to worry about ties when sorting.

Steps:

• 1. Pair each name with its corresponding height.

• 2. Sort the pairs based on height in descending order.

• 3. Extract the names from the sorted pairs and return them.

Empty Inputs:

• The problem guarantees at least one person in the input, so this case will not occur.

Large Inputs:

• Ensure the solution efficiently handles cases where n is close to 1000.

Special Values:

• If there is only one person, the list of names is trivially sorted.

Constraints:

• The number of names and heights will always match, and the heights are distinct.

  vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
    vector<pair<int, string>> A;
    int N = names.size();
    for(int i = 0; i < N; i++) {
        A.push_back({heights[i], names[i]});
    }

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

    vector<string> ans;
    for(int i = 0; i < N; i++) {
        ans.push_back(A[i].second);
    }
    return ans;
}

1 : Function Declaration

  vector<string> sortPeople(vector<string>& names, vector<int>& heights) {

This line defines the function 'sortPeople' which takes two arguments: a vector of names and a vector of heights. It returns a vector of strings (sorted names).

2 : Variable Initialization

    vector<pair<int, string>> A;

A vector of pairs is initialized to hold pairs of height (int) and name (string). This will be used to store the corresponding heights and names together.

3 : Variable Initialization

    int N = names.size();

The variable 'N' is set to the size of the 'names' vector, which gives the number of elements (people) to be processed.

4 : Loop

    for(int i = 0; i < N; i++) {

A loop is initiated to iterate through the list of names and heights.

5 : Push to Vector

        A.push_back({heights[i], names[i]});

Each height and corresponding name are added as a pair to the vector 'A'.

6 : Sorting

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

The vector 'A' is sorted in descending order based on the first element of the pairs (the heights), which is achieved using 'rbegin()' and 'rend()' to reverse the order.

7 : Result Initialization

    vector<string> ans;

An empty vector 'ans' is initialized to store the sorted names.

8 : Loop

    for(int i = 0; i < N; i++) {

Another loop is initiated to extract the sorted names from the vector 'A'.

9 : Push to Result

        ans.push_back(A[i].second);

The second element of each pair (the name) is pushed to the 'ans' vector.

10 : Return

    return ans;

The function returns the 'ans' vector containing the names sorted by their corresponding heights.

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: The time complexity is O(n log n) due to sorting the pairs.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) because we store the pairs of names and heights.

Leetcode 2418: Sort the People

Explore →