algoadvance

Given two lists names and heights of the same length n, where names[i] is the name of the ith person and heights[i] is the height of the ith person, return the 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"]

Example 2:

Input: names = ["Alice","Bob","Bob"], heights = [155,185,150]
Output: ["Bob","Alice","Bob"]

Constraints:

• n == names.length == heights.length
• 1 <= n <= 100
• 1 <= heights[i] <= 10^5
• names[i] consists of alphabets.

Clarifying Questions

1. Will there be duplicate heights?
   • Yes, heights can be the same for multiple people.
2. Is the order of names in the resulting list important when two people have the same height?
   • In the example provided, it does not specify how to handle tie cases. We can assume the stable sort property, meaning if two people have the same height, their relative order in the result should be the same as in the input list.

Strategy

1. Zip the names and heights lists together to create pairs of (name, height).
2. Sort these pairs based on height in descending order.
3. Extract and return the names from the sorted pairs.

Code

Here’s a Python implementation for the problem:

def sortPeople(names, heights):
    # Zip the names and heights together
    people = list(zip(names, heights))
    
    # Sort the zipped list by height in descending order
    people.sort(key=lambda x: x[1], reverse=True)
    
    # Extract the sorted names
    sorted_names = [person[0] for person in people]
    
    return sorted_names

Time Complexity

• Time Complexity: O(n log n), where n is the number of people. This comes from the sorting step.
• Space Complexity: O(n), due to the space required to store the list of tuples and the final sorted list of names.

This solution is efficient given the problem constraints. The space complexity is linear relative to the input size, and the time complexity is optimal for sorting.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?