Sort the People

2 min readUpdated 14 July 2025

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:

EXAMPLE_ENTITY

names = ["Mary","John","Emma"], heights = [180,165,170]

Output:

EXAMPLE_ENTITY

["Mary","Emma","John"]

Explanation:

EXAMPLE_ENTITY

Mary is the tallest, followed by Emma and John.

Example 2

Input:

EXAMPLE_ENTITY

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

Output:

EXAMPLE_ENTITY

["Bob","Alice","Bob"]

Explanation:

EXAMPLE_ENTITY

The first Bob is the tallest, followed by Alice and the second Bob.

Constraints

n == names.length == heights.length
1 <= n <= 103
1 <= names[i].length <= 20
1 <= heights[i] <= 105
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

Approach and Intuition

Understand the relationship between the two arrays:
- Both arrays are indexed such that names[i] is associated with heights[i].
- Each index i corresponds to a unique person's name and height.
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

CPP
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++;
        }
    }
};
Powered by Vultr AgentBeta

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 arrangePeople function initializes the sorting process, accepting two vectors people and measures. people contains names as strings, and measures holds associated heights as integers.
The sortHeights private 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 combine method 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 people and measures arrays, 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++;
        }
    }
}
Powered by Vultr AgentBeta

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
Powered by Vultr AgentBeta

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 arrangePeople method initiates the sorting process by calling a recursive helper method _recursive_sort for 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_sort method 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 _combine method 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 _combine method 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.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.

Sort the People

2 min readUpdated 14 July 2025

Problem Statement

Examples

Example 1

Input:

EXAMPLE_ENTITY

names = ["Mary","John","Emma"], heights = [180,165,170]

Output:

EXAMPLE_ENTITY

["Mary","Emma","John"]

Explanation:

EXAMPLE_ENTITY

Mary is the tallest, followed by Emma and John.

Example 2

Input:

EXAMPLE_ENTITY

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

Output:

EXAMPLE_ENTITY

["Bob","Alice","Bob"]

Explanation:

EXAMPLE_ENTITY

The first Bob is the tallest, followed by Alice and the second Bob.

Constraints

n == names.length == heights.length
1 <= n <= 103
1 <= names[i].length <= 20
1 <= heights[i] <= 105
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

Approach and Intuition

Understand the relationship between the two arrays:
- Both arrays are indexed such that names[i] is associated with heights[i].
- Each index i corresponds to a unique person's name and height.
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

CPP
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++;
        }
    }
};
Powered by Vultr AgentBeta

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 arrangePeople function initializes the sorting process, accepting two vectors people and measures. people contains names as strings, and measures holds associated heights as integers.
The sortHeights private 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 combine method 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 people and measures arrays, thus ensuring the array is sorted by height in descending order.

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++;
        }
    }
}
Powered by Vultr AgentBeta

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
Powered by Vultr AgentBeta

Understand the key elements of the solution:

The arrangePeople method initiates the sorting process by calling a recursive helper method _recursive_sort for 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_sort method 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 _combine method 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 _combine method 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.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.