Problem

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.

Examples

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.

Solution

This is mainly about sorting, but arrays are separate, so lets see how we can sort the name and height pairs. Please look at the video explanation below:

Method 1 - Sorting the pair

We can follow these steps:

  1. Pair each name with its corresponding height.
  2. Sort the pairs by the height in descending order.
  3. Extract the names from the sorted pairs.

Code

Java
public class Solution {
	static class Person {
		String name;
		int height;

		Person(String name, int height) {
			this.name = name;
			this.height = height;
		}
	}

	public static String[] sortPeople(String[] names, int[] heights) {
		int n = names.length;
		Person[] people = new Person[n];

		// Combine names and heights
		for (int i = 0; i < n; i++) {
			people[i] = new Person(names[i], heights[i]);
		}

		// Sort the array of Person objects by height in descending order
		Arrays.sort(people, (a, b) -> b.height - a.height);

		// Extract the names from the sorted Person array
		String[] sortedNames = new String[n];

		for (int i = 0; i < n; i++) {
			sortedNames[i] = people[i].name;
		}

		return sortedNames;
	}

}
Python
  1. Combining Names and Heights: We use the zip function to create pairs of names and heights.
  2. Sorting: We sort the list of tuples by height in descending order using the sort method with key=lambda x: x[1] and reverse=True.
  3. Extracting Names: Finally, we extract the names from the sorted list of tuples.
def sort_people(names, heights):
    # Combine names and heights into a list of tuples
    people = list(zip(names, heights))

    # Sort the list of tuples by height in descending order
    people.sort(key=lambda x: x[1], reverse=True)

    # Extract the names from the sorted list of tuples
    sorted_names = [person[0] for person in people]

    return sorted_names

Complexity

  • ⏰ Time complexity: O(n log n) where n is number of people
  • 🧺 Space complexity: O(n) for creating the pair of name and height.

Method 2 - Using Hashmap

As the pairs are distinct, we can use hashmap for storing height to name pair.

Code

Java
class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        Map<Integer, String> map = new HashMap<>();
        for (int i = 0; i < names.length; i++) {
            map.put(heights[i], names[i]);
        }        
        Arrays.sort(heights);
        String[] ans = new String[heights.length];
        int index = 0;
        for (int i = heights.length - 1; i >= 0; i--) {
            ans[index] = map.get(heights[i]);
            index++;
        }
        return ans;
    }
}

Method 3 - Using TreeMap

We can use TreeMap as well, as it keeps the heights in sorted order, so we don’t need to sort the heights array explicitly.

Code

Java
class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        Map<Integer,String> map = new TreeMap<>(Collections.reverseOrder());
        
        for(int i=0;i<names.length;i++) {
            map.put(heights[i],names[i]);
        }
        
        String[] ans = new String[names.length];
        int index=0; 
        for(Integer height : map.keySet())
            {
                ans[index] = map.get(height);
                index++;
            }

        return ans;
    }
}