2418. Sort the People
Problem Description
In this problem, we are given two arrays: names
and heights
. Both arrays have the same length, n
, and for any given index i
, names[i]
represents the name of a person, and heights[i]
represents their respective height. The heights
array is made up of distinct positive integers, which means no two people can have the same height.
Our task is to sort the people by their heights in descending order, i.e., from the tallest to the shortest person. The output should be a reordered names
array that reflects this sorting by height.
Understanding the problem involves recognizing that we need to maintain the association between each person's name and their height while sorting, which is commonly known as a "sort by keys" problem where the heights serve as keys, and the names are the values associated with those keys.
Intuition
The solution to this problem requires a sorting strategy. Since each person's height is unique (there are no duplicates), we can sort the people based on their heights in descending order. However, rather than sorting heights
directly, we need to sort indices that can then be used to reorder the names
.
Here's the intuitive breakdown of the solution:
- Generate a list of indices
idx
from0
ton-1
wheren
is the length of the heights array. - Sort the
idx
list, but instead of sorting it in the usual ascending order, we use a custom sorting key. The key is a function that takes an indexi
and returns the negative ofheights[i]
. By using the negative value, we effectively sort the indices in order of descending heights since the usual sorting is in ascending order. - After sorting the indices in this way, we can create a new list with names in the proper order. We do this by iterating through the sorted
idx
list and fetching the corresponding name from thenames
list for each sorted index.
This approach allows us to sort the names
list according to the descending order of the heights without losing the association between names and their corresponding heights.
Learn more about Sorting patterns.
Solution Approach
The implementation of the solution involves a few key steps, and it employs basic list manipulation and sorting techniques in Python. Here's a step-by-step walkthrough of the algorithm and patterns used:
-
Initialization of index list: We create a list called
idx
which contains indices from0
ton-1
, wheren
is the length of theheights
array. This is accomplished with therange
function in Python, which returns a sequence of numbers. We convert it to a list using the built-inlist
function.idx = list(range(len(heights)))
-
Custom Sorting: We want to sort the indices based on the values in
heights
array but in descending order. To do this, we use thesort
method of the list. Thesort
method is modified by a custom key function, which is passed as a lambda function. The lambda function takes each indexi
and returns-heights[i]
, which ensures that we are sorting in descending order based on height values.idx.sort(key=lambda i: -heights[i])
-
Reordering names by sorted indices: With the indices sorted in the correct order, the final step is to reorder the
names
according to these indices. We accomplish this by iterating over theidx
and using a list comprehension to create a new list. For eachi
inidx
, we fetchnames[i]
and add it to the new list.return [names[i] for i in idx]
This approach leverages a key aspect of Python's sorting capabilities, where sort is stable and can be customized easily with a key function. By inverting the heights in the key function (using negative heights), we avoid the need to write a custom comparison function; the sort method automatically handles it for us.
This solution is efficient because it does not involve any complicated data structures or algorithms beyond basic list operations and sorting, and it maintains a time complexity of O(n log n), where n
is the number of people in the list. The custom key function does not significantly affect this complexity, as it simply changes the values used for comparison during the sort process.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have the following lists of names and heights:
names = ['Alice', 'Bob', 'Charlie', 'Dana'] heights = [155, 165, 160, 170]
We can see that Dana is the tallest, followed by Bob, then Charlie, and finally Alice. We want to sort the names
array so that it matches the descending order of heights
. Following the steps in the solution approach:
-
Initialization of index list: We create a list of indices which will correspond to the indices of the
heights
list.idx = list(range(len(heights))) # idx will be [0, 1, 2, 3]
-
Custom Sorting: Now we sort
idx
by the heights in descending order by using the negative heights as the key for sorting.idx.sort(key=lambda i: -heights[i]) # After sorting, idx will be [3, 1, 2, 0]
The index
3
comes first asheights[3]
(which is 170) is the greatest, and so on. -
Reordering names by sorted indices: Using our sorted
idx
, we reordernames
by mapping each index to the corresponding name.sorted_names = [names[i] for i in idx] # This gives us ['Dana', 'Bob', 'Charlie', 'Alice']
Now, when we look at sorted_names
, we have the names ordered by descending height:
print(sorted_names) # Output: ['Dana', 'Bob', 'Charlie', 'Alice']
This matches our expectations based on the heights. The sorted_names
list is the resultant list where the corresponding names are ordered from the tallest to the shortest person. This example clearly demonstrates the efficacy of the solution approach for the problem described.
Solution Implementation
1from typing import List
2
3class Solution:
4 def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
5 # This method sorts the people based on descending order of their heights.
6 # It then returns a list of names of the people sorted by their heights.
7
8 # Generate an index list that matches the indexes of the heights list.
9 indices = list(range(len(heights)))
10
11 # Sort the indices list based on descending values of heights.
12 # The lambda function returns the negated height value for each index, sorting in descending order.
13 indices.sort(key=lambda i: -heights[i])
14
15 # Map the sorted indices to their corresponding names.
16 # This results in a list of names ordered by descending height.
17 sorted_names = [names[i] for i in indices]
18
19 # Return the list of sorted names.
20 return sorted_names
21
22# Example usage:
23# If we have two lists, one of names and one of the corresponding heights:
24# names = ["Mary", "John", "Emma"]
25# heights = [160, 180, 165]
26# solution = Solution()
27# sorted_people = solution.sortPeople(names, heights)
28# The output will be: ["John", "Emma", "Mary"]
29
1import java.util.Arrays;
2
3class Solution {
4 public String[] sortPeople(String[] names, int[] heights) {
5 // Extract the number of elements from the names array, which also applies to the heights array.
6 int numberOfPeople = names.length;
7
8 // Create an array of indices representing each person.
9 Integer[] indices = new Integer[numberOfPeople];
10
11 // Initialize the indices array with values from 0 to numberOfPeople - 1.
12 for (int i = 0; i < numberOfPeople; ++i) {
13 indices[i] = i;
14 }
15
16 // Sort the indices array based on the descending order of heights using a custom comparator.
17 // The comparator computes the difference between the heights at indices j and i.
18 Arrays.sort(indices, (i, j) -> heights[j] - heights[i]);
19
20 // Create a result array to store the sorted names based on the heights.
21 String[] sortedNames = new String[numberOfPeople];
22
23 // Build the result array by mapping sorted indices to their respective names.
24 for (int i = 0; i < numberOfPeople; ++i) {
25 sortedNames[i] = names[indices[i]];
26 }
27
28 // Return the array of names sorted by descending heights.
29 return sortedNames;
30 }
31}
32
1#include <algorithm> // include the algorithm header for std::sort and std::iota functions
2#include <numeric> // include the numeric header for std::iota function
3#include <string> // include the string header for using std::string
4#include <vector> // include the vector header for using std::vector
5
6class Solution {
7public:
8 // This function sorts people by their heights in descending order
9 // Arguments:
10 // names - a vector of strings representing people's names
11 // heights - a vector of integers representing corresponding people's heights
12 // Returns:
13 // A vector of strings representing people's names sorted by their heights in descending order
14 vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
15 int numPeople = names.size(); // get the number of people
16 vector<int> indices(numPeople); // create a vector to hold indices
17 iota(indices.begin(), indices.end(), 0); // fill the vector with consecutive numbers starting at 0
18
19 // Use sort function with custom comparator to sort the indices based on descending order of heights
20 sort(indices.begin(), indices.end(), [&](int i, int j) {
21 return heights[i] > heights[j];
22 });
23
24 vector<string> sortedNames; // create a vector to hold the sorted names
25 sortedNames.reserve(numPeople); // reserve space in the vector for numPeople elements
26
27 // Construct the sorted names vector based on the sorted indices
28 for (int index : indices) {
29 sortedNames.push_back(names[index]); // add name to the result vector in sorted order
30 }
31
32 return sortedNames; // return the sorted names
33 }
34};
35
1function sortPeople(names: string[], heights: number[]): string[] {
2 // Get the number of people from the length of the names array.
3 const numberOfPeople = names.length;
4 // Initialize an index array to keep track of original indices.
5 const indices = new Array(numberOfPeople);
6 // Fill the index array with indices from 0 to numberOfPeople - 1.
7 for (let i = 0; i < numberOfPeople; ++i) {
8 indices[i] = i;
9 }
10 // Sort the index array based on heights in descending order.
11 // The sort compares the heights at the indices and sorts the indices array.
12 indices.sort((index1, index2) => heights[index2] - heights[index1]);
13 // Initialize an array to store the sorted names.
14 const sortedNames: string[] = [];
15 // Iterate over the sorted indices and push the corresponding name
16 // into the sortedNames array.
17 for (const index of indices) {
18 sortedNames.push(names[index]);
19 }
20 // Return the array of sorted names.
21 return sortedNames;
22}
23
Time and Space Complexity
Time Complexity
The time complexity of the given code is primarily determined by the sorting operation. The sort
method on the idx
list is using a custom key, which is based on the values of the heights
list. Sorting in Python is implemented with the Timsort algorithm, which has a time complexity of O(n log n)
in the average and worst case, where n
is the number of elements to be sorted.
In the given code, the list idx
has a length equal to that of names
and heights
, so there will be n
items to sort, where n
represents the length of either names
or heights
.
Hence, the overall time complexity is O(n log n)
.
Space Complexity
The space complexity of this function can be analyzed by looking at the additional memory used by the program.
- The list
idx
is created which will holdn
integers. This contributesO(n)
space. - The sorting operation may temporarily require additional space to hold elements when sorting, contributing an additional
O(log n)
space due to the recursion stack of Timsort. - After sorting, a new list comprehension is used to generate the result list based on the sorted indices. This list will also be of length
n
, which means an additionalO(n)
space.
As the dominant term in space complexity is O(n)
(the space used for storing indices and the final output list), we can conclude the overall space complexity of the given code is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!