Problem Statement
In this problem, you are provided with two arrays: one containing strings (names), and the other containing distinct positive integers (heights). Both arrays have the same length, n. The element at each index i in names corresponds to the name of a person, and the element at the same index in heights refers to that person's height. Your task is to rearrange the names array so that the names are sorted according to their corresponding heights in descending order. Essentially, the name of the tallest person should appear first, followed by the second tallest, and so on, all the way down to the shortest.
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.
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.
Approach and Intuition
Understand the relationship between the two arrays:
- Both arrays are indexed such that
names[i]is associated withheights[i]. - Each index
icorresponds to a unique person's name and height.
- Both arrays are indexed such that
Map each person's height to their name:
- Use a data structure that can store pairs of values (such as tuples in Python).
- Combine each name with its respective height into this structure to maintain the association.
Sort the combined structure:
- Since you need the names sorted by decreasing height, sort these pairs based primarily on the height values in descending order.
- Use any efficient sorting algorithm or built-in sorting method which can consider a custom key (like the second element in each pair when pairs are in the form (name, height)).
Extract the sorted names:
- Once sorting is complete, iterate through the sorted structure to collect the names in their new order.
- The heights are only used for sorting and do not need to be returned or maintained separately after sorting.
Each step ensures minimal computation while guaranteeing that the final array of names is correctly ordered by decreasing height, resonating with the principle of sorting based on associated values.
Solutions
- C++
class Solution {
public:
vector<string> arrangePeople(vector<string>& people, vector<int>& measures) {
sortHeights(measures, people, 0, measures.size() - 1);
return people;
}
private:
void sortHeights(vector<int>& measures, vector<string>& people, int low,
int high) {
if (low < high) {
int middle = low + (high - low) / 2;
sortHeights(measures, people, low, middle);
sortHeights(measures, people, middle + 1, high);
combine(people, measures, low, middle, high);
}
}
void combine(vector<string>& people, vector<int>& measures, int low, int middle,
int high) {
int sizeLeft = middle - low + 1;
int sizeRight = high - middle;
// Temporary storage
vector<int> tempLeft(sizeLeft);
vector<int> tempRight(sizeRight);
vector<string> tempPeopleLeft(sizeLeft);
vector<string> tempPeopleRight(sizeRight);
// Fill temporary storage
for (int i = 0; i < sizeLeft; i++) {
tempLeft[i] = measures[low + i];
tempPeopleLeft[i] = people[low + i];
}
for (int j = 0; j < sizeRight; j++) {
tempRight[j] = measures[middle + 1 + j];
tempPeopleRight[j] = people[middle + 1 + j];
}
// Perform the merge
int indexLeft = 0, indexRight = 0;
int indexMerge = low;
while (indexLeft < sizeLeft && indexRight < sizeRight) {
if (tempLeft[indexLeft] >= tempRight[indexRight]) {
measures[indexMerge] = tempLeft[indexLeft];
people[indexMerge] = tempPeopleLeft[indexLeft];
indexLeft++;
} else {
measures[indexMerge] = tempRight[indexRight];
people[indexMerge] = tempPeopleRight[indexRight];
indexRight++;
}
indexMerge++;
}
// Handle leftovers if any
while (indexLeft < sizeLeft) {
measures[indexMerge] = tempLeft[indexLeft];
people[indexMerge] = tempPeopleLeft[indexLeft];
indexLeft++;
indexMerge++;
}
while (indexRight < sizeRight) {
measures[indexMerge] = tempRight[indexRight];
people[indexMerge] = tempPeopleRight[indexRight];
indexRight++;
indexMerge++;
}
}
};
The provided C++ solution is designed to reorder an array of people based on their heights. This sorting process uses a customized merge sort algorithm that is implemented through recursion.
- The
arrangePeoplefunction initializes the sorting process, accepting two vectorspeopleandmeasures.peoplecontains names as strings, andmeasuresholds associated heights as integers. - The
sortHeightsprivate method facilitates the recursive merge sort. It divides the array into smaller segments until individual elements are reached and then merges these segments in sorted order based on heights. - The
combinemethod performs the merging of two sorted segments. Temporary vectors for left and right segments store names and measures, aiding in sorting and merging. - During the merge process, comparisons occur between left and right segment elements. Depending on the outcome of this comparison (comparing heights), the elements from either the left or the right temporary storage arrays are systematically transferred back to the original
peopleandmeasuresarrays, thus ensuring the array is sorted by height in descending order.
Overall, the function not only sorts the heights in descending order but also rearranges the people array so that names correspond to the sorted order of measures. This ensures the people are sorted according to their heights effectively.
- Java
class Solution {
public String[] arrangePeople(String[] peopleNames, int[] peopleHeights) {
sortData(peopleNames, peopleHeights, 0, peopleHeights.length - 1);
return peopleNames;
}
private void sortData(String[] peopleNames, int[] peopleHeights, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
sortData(peopleNames, peopleHeights, low, mid);
sortData(peopleNames, peopleHeights, mid + 1, high);
combine(peopleNames, peopleHeights, low, mid, high);
}
}
private void combine(
String[] peopleNames,
int[] peopleHeights,
int low,
int mid,
int high
) {
int n1 = mid - low + 1;
int n2 = high - mid;
// Temp arrays
int[] leftHeights = new int[n1];
int[] rightHeights = new int[n2];
String[] leftNames = new String[n1];
String[] rightNames = new String[n2];
// Fill temp arrays
for (int i = 0; i < n1; i++) {
leftHeights[i] = peopleHeights[low + i];
leftNames[i] = peopleNames[low + i];
}
for (int j = 0; j < n2; j++) {
rightHeights[j] = peopleHeights[mid + 1 + j];
rightNames[j] = peopleNames[mid + 1 + j];
}
// Merge the arrays in descending order
int leftPointer = 0, rightPointer = 0;
int mergedPosition = low;
while (leftPointer < n1 && rightPointer < n2) {
if (leftHeights[leftPointer] >= rightHeights[rightPointer]) {
peopleHeights[mergedPosition] = leftHeights[leftPointer];
peopleNames[mergedPosition] = leftNames[leftPointer];
leftPointer++;
} else {
peopleHeights[mergedPosition] = rightHeights[rightPointer];
peopleNames[mergedPosition] = rightNames[rightPointer];
rightPointer++;
}
mergedPosition++;
}
// Remaining elements from left array
while (leftPointer < n1) {
peopleHeights[mergedPosition] = leftHeights[leftPointer];
peopleNames[mergedPosition] = leftNames[leftPointer];
leftPointer++;
mergedPosition++;
}
// Remaining elements from right array
while (rightPointer < n2) {
peopleHeights[mergedPosition] = rightHeights[rightPointer];
peopleNames[mergedPosition] = rightNames[rightPointer];
rightPointer++;
mergedPosition++;
}
}
}
The "Sort the People" solution in Java is a structured implementation of the Merge Sort algorithm to sort an array of names based on their corresponding heights. This implementation involves sorting the names in descending order according to heights.
Here is a breakdown of the key components and their roles:
arrangePeople Function: This is the interface method that accepts an array of people's names and their corresponding heights. It initiates the sorting process and returns the sorted names.
sortData Function: This recursive helper function is employed to divide the array into subarrays until they contain a single element, utilizing the divide-and-conquer methodology integral to Merge Sort.
combine Function: Post division, this function merges the subarrays. It ensures that the merge is done in such a manner that the resultant array is sorted in descending order by height. It simultaneously rearranges the names array to match the sorted order of heights.
The process of sorting involves several internal steps:
- The original array is continually split into smaller ones until each subarray contains a single element.
- These subarrays are then merged back together in a manner that the heights are in descending order, restructuring the names to maintain corresponding order with the sorted heights.
Considerations are also made for:
- Efficient space usage by creating temporary arrays only during the merge process.
- Handling remaining elements in either left or right subarrays, ensuring no data is lost during merging.
With this structured approach using Merge Sort, the solution ensures a time complexity of O(n log n), making it efficient for sorting even large datasets.
- Python
class Solution:
def arrangePeople(self, people_names: List[str], people_heights: List[int]) -> List[str]:
self._recursive_sort(people_names, people_heights, 0, len(people_heights) - 1)
return people_names
def _recursive_sort(
self, people_names: List[str], people_heights: List[int], start: int, end: int
):
if start < end:
pivot = start + (end - start) // 2
self._recursive_sort(people_names, people_heights, start, pivot)
self._recursive_sort(people_names, people_heights, pivot + 1, end)
self._combine(people_names, people_heights, start, pivot, end)
def _combine(
self,
people_names: List[str],
people_heights: List[int],
start: int,
mid: int,
end: int,
):
left_part = mid - start + 1
right_part = end - mid
# Temporary lists for merge sections
left_heights = people_heights[start : start + left_part]
right_heights = people_heights[mid + 1 : mid + 1 + right_part]
left_names = people_names[start : start + left_part]
right_names = people_names[mid + 1 : mid + 1 + right_part]
# Variables for iterating through temporary lists
i, j = 0, 0
k = start
while i < left_part and j < right_part:
if (
left_heights[i] >= right_heights[j]
): # Maintain descending order
people_heights[k] = left_heights[i]
people_names[k] = left_names[i]
i += 1
else:
people_heights[k] = right_heights[j]
people_names[k] = right_names[j]
j += 1
k += 1
# Copy any remaining elements of the lists
while i < left_part:
people_heights[k] = left_heights[i]
people_names[k] = left_names[i]
i += 1
k += 1
while j < right_part:
people_heights[k] = right_heights[j]
people_names[k] = right_names[j]
j += 1
k += 1
In the provided Python solution, the aim is to sort a list of people by their heights in descending order and return the names in their newly sorted order. It utilizes a merge sort algorithm, which is a type of divide and conquer algorithm, to efficiently achieve this sorting.
Understand the key elements of the solution:
The
arrangePeoplemethod initiates the sorting process by calling a recursive helper method_recursive_sortfor the entire range of the indices from the people list. This method finalizes and returns the names sorted according to their corresponding heights.The
_recursive_sortmethod recursively divides the list into halves until it reaches lists of single elements. This is achieved by calculating the pivot as the midpoint of the current segment of the list it is handling.The
_combinemethod is then called to merge the sorted halves back together in a way that maintains the order by height in descending. During the merge, elements are compared between the left and right temporary lists, and the larger height (as the sort is descending) is placed first in the merged list.Temporary arrays are used in the
_combinemethod to facilitate the merging. Copies of subarrays of names and heights are made that correspond to the currently considered segments.Merge operations consider both lists; elements are compared and merged back onto the original list accordingly. If any elements remain in the temporary lists after the primary merging loop (either because they are larger or because their respective half was bigger), these are appended thereafter to ensure all elements are included.
This structured approach ensures efficient sorting with a time complexity typically in the order of O(n log n), which is optimal for comparison-based sorting. The recursion helps in breaking the problem down into manageable sub-problems, which are then merged to form the sorted list, ensuring that the final order respects the desired descending order by height, using the merge sort's well-known stable characteristics.
No comments yet.