# Sort the People
**Difficulty:** EASY
[External](https://leetcode.com/problems/sort-the-people)
Canonical: https://scaleengineer.com/dsa/problems/sort-the-people
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## 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.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.

# Approaches
## Brute Force with Nested Loops
This approach directly simulates the sorting process without using advanced data structures or sorting algorithms. It repeatedly finds the tallest person among the remaining unsorted people and places their name in the correct position in the result array. This is analogous to a Selection Sort.
**Time:** O(n^2) - The code has nested loops. The outer loop runs `n` times, and for each iteration, the inner loop also runs `n` times to find the maximum height among the remaining people. · **Space:** O(n) - We use an additional boolean array `visited` of size `n` and a `result` array of size `n`.
**Pros:** Conceptually simple and easy to implement from scratch.; Does not require knowledge of complex data structures or built-in sorting functions.
**Cons:** Highly inefficient with a time complexity of O(n^2), making it unsuitable for large datasets.
### Explanation
The algorithm works as follows:
1. We create a result array `sortedNames` to store the final sorted list of names and a boolean array `visited` of the same size `n` to keep track of people who have already been placed in the result.
2. We then loop `n` times, once for each position in the `sortedNames` array.
3. In each iteration of this outer loop, we perform a linear scan through the entire `heights` array to find the person with the maximum height who has not been `visited` yet. We keep track of this person's index.
4. Once the tallest unvisited person is found, we add their name to the current position in the `sortedNames` array and mark their index as `visited`.
5. This process is repeated until all positions in `sortedNames` are filled. The final array is then returned.
```java
class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        String[] result = new String[n];
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            int maxHeight = -1;
            int maxIndex = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && heights[j] > maxHeight) {
                    maxHeight = heights[j];
                    maxIndex = j;
                }
            }
            result[i] = names[maxIndex];
            visited[maxIndex] = true;
        }
        return result;
    }
}
```
### Algorithm
- 1. Initialize a new string array `result` of size `n`.
- 2. Initialize a boolean array `visited` of size `n` with all values as `false`.
- 3. Loop from `i = 0` to `n-1`:
    a. Initialize `maxIndex = -1` and `maxHeight = -1`.
    b. Loop from `j = 0` to `n-1`:
        i. If `visited[j]` is `false` and `heights[j]` is greater than `maxHeight`, update `maxHeight` to `heights[j]` and `maxIndex` to `j`.
    c. Place the name of the found person in the result: `result[i] = names[maxIndex]`.
    d. Mark the person as visited: `visited[maxIndex] = true`.
- 4. Return the `result` array.

## Pairing and Sorting
A much more efficient method is to link each name with its height. This can be done by creating a custom data structure (like a `Person` class) or using a 2D array to hold pairs of (height, name). After creating these pairs, we can use a standard, efficient sorting algorithm to sort the pairs based on height in descending order. Finally, we can iterate through the sorted pairs to construct the final sorted list of names.
**Time:** O(n log n) - The dominant operation is sorting the array of pairs. Creating the pairs and extracting the names are both O(n) operations. · **Space:** O(n) - We need an auxiliary array of size `n` to store the `Person` objects.
**Pros:** Significantly more efficient (O(n log n)) than the brute-force approach.; A general and common pattern for sorting related data.; Relatively easy to implement using built-in sorting utilities.
**Cons:** Requires extra space (O(n)) to store the pairs.; Involves creating a helper class or structure, which adds a bit of boilerplate code.
### Explanation
This approach involves three main steps:
1. **Pairing:** We create a custom class, say `Person`, to encapsulate the `name` and `height` of an individual. We then iterate through the input arrays and create an array of `Person` objects, where each object `people[i]` corresponds to `names[i]` and `heights[i]`.
2. **Sorting:** We use a built-in sorting function, such as `Arrays.sort()` in Java. We provide a custom comparator that instructs the sort function to arrange the `Person` objects in descending order based on their `height` attribute. This step is the core of the approach and is typically very efficient (O(n log n)).
3. **Extraction:** After the `people` array is sorted, we create a new string array for the result. We then iterate through the sorted `people` array and extract the `name` from each `Person` object, placing it into our result array.
```java
class Solution {
    class Person {
        String name;
        int height;
        Person(String name, int height) {
            this.name = name;
            this.height = height;
        }
    }

    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Person[] people = new Person[n];
        for (int i = 0; i < n; i++) {
            people[i] = new Person(names[i], heights[i]);
        }

        // Sort in descending order of height
        Arrays.sort(people, (a, b) -> b.height - a.height);

        String[] result = new String[n];
        for (int i = 0; i < n; i++) {
            result[i] = people[i].name;
        }
        return result;
    }
}
```
### Algorithm
- 1. Define a helper class or structure (e.g., `Person`) to store a name and a height together.
- 2. Create an array or list of these `Person` objects, `people`, of size `n`.
- 3. Iterate from `i = 0` to `n-1`, populating the `people` collection with `(names[i], heights[i])`.
- 4. Sort the `people` collection in descending order based on the `height` attribute using a standard sorting algorithm.
- 5. Create a new string array `result` of size `n`.
- 6. Iterate through the sorted `people` collection and populate the `result` array with the names.
- 7. Return the `result` array.

## Using a Map
This approach leverages a map data structure to associate heights with names. Since all heights are distinct, they can serve as unique keys. By using a sorted map, such as a `TreeMap` in Java, we can automatically maintain the people in sorted order by height. This leads to a very clean and concise solution.
**Time:** O(n log n) - Inserting `n` elements into a `TreeMap` takes O(n log n) time, as each insertion is an O(log k) operation where `k` is the current size of the map. Retrieving the values is an O(n) operation. · **Space:** O(n) - The `TreeMap` needs to store `n` key-value pairs.
**Pros:** Very elegant and concise code.; Effectively uses built-in data structures to handle the sorting logic implicitly.; Avoids the need for a custom helper class.
**Cons:** The performance might have a slightly higher constant factor overhead compared to sorting a simple array of custom objects, depending on the `TreeMap` implementation.
### Explanation
The core idea is to use the heights as keys and names as values in a map. A `TreeMap` is ideal because it keeps its keys sorted.
1. We instantiate a `TreeMap` and provide it with a reverse order comparator (`Collections.reverseOrder()`). This ensures that as we add entries, the map will automatically sort them by key (height) in descending order.
2. We iterate through the input arrays once, from `i = 0` to `n-1`. In each iteration, we insert a key-value pair `(heights[i], names[i])` into the `TreeMap`.
3. After the loop finishes, the `TreeMap` contains all the people, sorted by height from tallest to shortest.
4. The `values()` collection of the `TreeMap` will now provide the names in the desired sorted order. We can simply convert this collection to an array and return it.
```java
import java.util.Map;
import java.util.TreeMap;
import java.util.Collections;

class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Map<Integer, String> map = new TreeMap<>(Collections.reverseOrder());

        for (int i = 0; i < n; i++) {
            map.put(heights[i], names[i]);
        }

        return map.values().toArray(new String[0]);
    }
}
```
### Algorithm
- 1. Create a `TreeMap` that maps `Integer` keys (heights) to `String` values (names). Initialize it with a comparator for descending order.
- 2. Iterate from `i = 0` to `n-1` and insert each `(heights[i], names[i])` pair into the map.
- 3. The `TreeMap` automatically maintains the entries sorted by key in descending order.
- 4. Retrieve the collection of values (names) from the map. This collection will be in the correct sorted order.
- 5. Convert the collection of values to a string array and return it.

# Solutions
### Java

```java
class Solution { public String [] sortPeople ( String [] names , int [] heights ) { int n = names . length ; Integer [] idx = new Integer [ n ]; for ( int i = 0 ; i < n ; ++ i ) { idx [ i ] = i ; } Arrays . sort ( idx , ( i , j ) -> heights [ j ] - heights [ i ]); String [] ans = new String [ n ]; for ( int i = 0 ; i < n ; ++ i ) { ans [ i ] = names [ idx [ i ]]; } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < string > sortPeople ( vector < string >& names , vector < int >& heights ) { int n = names . size (); vector < int > idx ( n ); iota ( idx . begin (), idx . end (), 0 ); sort ( idx . begin (), idx . end (), [ & ]( int i , int j ) { return heights [ j ] < heights [ i ]; }); vector < string > ans ; for ( int i : idx ) { ans . push_back ( names [ i ]); } return ans ; } };
```

### Python

```python
class Solution : def sortPeople ( self , names : List [ str ], heights : List [ int ]) -> List [ str ]: idx = list ( range ( len ( heights ))) idx . sort ( key = lambda i : - heights [ i ]) return [ names [ i ] for i in idx ]
```