2418. Sort the People

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 index i, names[i] and heights[i] denote the name and height of the ith person.

Return names sorted in descending order by the people’s heights.

Example 1:

Input: names = ["Mary","John","Emma"], heights = [180,165,170]
Output: ["Mary","Emma","John"]
Explanation: Mary is the tallest, followed by Emma and John.

Example 2:

Input: names = ["Alice","Bob","Bob"], heights = [155,185,150]
Output: ["Bob","Alice","Bob"]
Explanation: The first Bob is the tallest, followed by Alice and the second Bob.

Constraints:

• n == names.length == heights.length
• 1 <= n <= 103
• 1 <= names[i].length <= 20
• 1 <= heights[i] <= 105
• names[i] consists of lower and upper case English letters.
• All the values of heights are distinct.

Approach 01:

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        std::unordered_map<int, std::string> data;
        int n = names.size();
        std::vector<std::string> result;

        for (int i = 0; i < n; ++i) {
            data[heights[i]] = names[i];
        }

        std::sort(heights.begin(), heights.end(), std::greater<int>());

        for (int i = 0; i < n; ++i) {
            result.push_back(data[heights[i]]);
        }

        return result;
    }
};

from typing import *

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        data = {}
        n = len(names)
        result = []

        for i in range(n):
            data[heights[i]] = names[i]
        
        heights.sort()
        heights = heights[::-1]
        for i in range(n):
            result.append(data[heights[i]])
        return result

Time Complexity

• HashMap Population:

  Inserting each name-height pair into the std::unordered_map data takes \( O(n) \) time, where \( n \) is the number of names and heights.

• Sorting:

  Sorting the heights vector in descending order using std::sort takes \( O(n \log n) \) time.

• Result Population:

  Creating the result vector by mapping sorted heights to names using the data hashmap takes \( O(n) \) time.

• Overall Time Complexity:

  The overall time complexity is dominated by the sorting step, resulting in \( O(n \log n) \).

Space Complexity

• Auxiliary Space:

  The data hashmap stores \( n \) name-height pairs, leading to \( O(n) \) space usage.

• Result Vector:

  The result vector result stores \( n \) names, leading to \( O(n) \) space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \), accounting for the space used by the data hashmap and the result vector.