Sort the People

Easy

#2202Time: 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`.1 company

Algorithms

Sorting

Data structures

Array Hash Table String

Companies

Infosys

Prompt

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 i^th 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 <= 10³
1 <= names[i].length <= 20
1 <= heights[i] <= 10⁵
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

1. Initialize a new string array result of size n.
1. Initialize a boolean array visited of size n with all values as false.
1. 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.
1. Return the result array.

Walkthrough

The algorithm works as follows:

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.
We then loop n times, once for each position in the sortedNames array.
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.
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.
This process is repeated until all positions in sortedNames are filled. The final array is then returned.

1class Solution {2    public String[] sortPeople(String[] names, int[] heights) {3        int n = names.length;4        String[] result = new String[n];5        boolean[] visited = new boolean[n];6 7        for (int i = 0; i < n; i++) {8            int maxHeight = -1;9            int maxIndex = -1;10            for (int j = 0; j < n; j++) {11                if (!visited[j] && heights[j] > maxHeight) {12                    maxHeight = heights[j];13                    maxIndex = j;14                }15            }16            result[i] = names[maxIndex];17            visited[maxIndex] = true;18        }19        return result;20    }21}

Complexity

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`.

Trade-offs

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.

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.

Algorithm

1. Define a helper class or structure (e.g., Person) to store a name and a height together.
1. Create an array or list of these Person objects, people, of size n.
1. Iterate from i = 0 to n-1, populating the people collection with (names[i], heights[i]).
1. Sort the people collection in descending order based on the height attribute using a standard sorting algorithm.
1. Create a new string array result of size n.
1. Iterate through the sorted people collection and populate the result array with the names.
1. Return the result array.

Walkthrough

This approach involves three main steps:

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].
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)).
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.

1class Solution {2    class Person {3        String name;4        int height;5        Person(String name, int height) {6            this.name = name;7            this.height = height;8        }9    }10 11    public String[] sortPeople(String[] names, int[] heights) {12        int n = names.length;13        Person[] people = new Person[n];14        for (int i = 0; i < n; i++) {15            people[i] = new Person(names[i], heights[i]);16        }17 18        // Sort in descending order of height19        Arrays.sort(people, (a, b) -> b.height - a.height);20 21        String[] result = new String[n];22        for (int i = 0; i < n; i++) {23            result[i] = people[i].name;24        }25        return result;26    }27}

Complexity

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.

Trade-offs

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.

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.

Algorithm

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

Walkthrough

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.

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.
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.
After the loop finishes, the TreeMap contains all the people, sorted by height from tallest to shortest.
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.

1import java.util.Map;2import java.util.TreeMap;3import java.util.Collections;4 5class Solution {6    public String[] sortPeople(String[] names, int[] heights) {7        int n = names.length;8        Map<Integer, String> map = new TreeMap<>(Collections.reverseOrder());9 10        for (int i = 0; i < n; i++) {11            map.put(heights[i], names[i]);12        }13 14        return map.values().toArray(new String[0]);15    }16}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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 ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class 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 ; } }

1class 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 ; } };

1class 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 ]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.