Algorithms and Data Structures in Python: Beginner Array Problem - Sort the People
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.
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.length1 <= n <= 1031 <= names[i].length <= 201 <= heights[i] <= 105names[i]consists of lower and upper case English letters.- All the values of
heightsare distinct.
Solution
def sort_by_height(names, heights):
combined = zip(names, heights) # Key Point 1
sorted_combined = sorted(combined, key=lambda x: x[1], reverse=True) # Key Point 2
return [name for name, _ in sorted_combined] # Key Point 3Key Point1: Combining names and heights with zip
The zipp() function pairs each element of the names array with the corresponding element in the heights array, creating an iterator of tuples. This operation effectively maps each name to its respective height, preparing the data for sorting based on these heights.
Key Point 2: Sorting with sorted and lambda
The sorted function, combined with a lambda function as the key, sorts the paired tuples by height in descending order. The lambda x: x[1] extracts the height from each tuple for comparison, and reverse=True ensures the sorting is done from tallest to shortest, aligning the names according to their heights.
Key Point 3: Extracting and Returning Names
A list comprehension iterates over the sorted tuples, extracting and returning only the names in a new list. This step discards the heights, leaving a list of names sorted in descending order by height, directly addressing the problem’s requirement to reorder names by the height of the individuals.
Time Complexity Analysis
The overall time complexity is dominated by the sorting step, which is O(n*log(n)). The other operations (zip() and the list comprehension) have linear time complexities, but when combined, they do not exceed the complexity of sorting.
Space Complexity Analysis
The overall space complexity is . The space required is primarily for the output of the zip function and the final list of sorted names. Although temporary space is also used during the sorting process, the dominant factor is the space required for storing the combined and then sorted elements.
Conclusion
This is it! For those eager to dive deeper into the world of algorithms in Python, I encourage you to explore my collection of tutorials. Whether you’re at the beginning of your coding journey or looking to sharpen your skills, there’s something for everyone.
As we wrap up this challenge, I hope it inspires you to explore further and embrace the continuous learning that programming demands. If you found this insight helpful, consider giving a clap and following for more algorithm and data structures problems. Let’s keep pushing the boundaries of what we can achieve with code, one problem at a time. Happy coding!
🚀 Boost Your Productivity with Notion
New to Notion? Discover how it can revolutionize your productivity
Ready to take your productivity to the next level? Integrate this content into your Notion workspace with ease:
1 Access the Notion Version of this Content
2 Look for the Duplicate button at the top-right corner of the page
3 Click on it to add this valuable resource to your Notion workspace
Seamlessly integrate this guide into your Notion workspace for easy access and swift reference. Leverage Notion AI to search and extract crucial insights, enhancing your productivity. Start curating your knowledge hub with Notion AI today and maximize every learning moment.
