Sort the People — Solution in Python, Java & C++
Sort the People solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and TCS.
Sort the People is an easy coding problem on arrays, hash table and sorting, asked in Amazon, TCS and Infosys interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting
- Asked at: Amazon, TCS, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A CodeKairo team photo is being arranged. You are given names, the members' names, and heights, where heights[i] is the height of names[i]. All heights are distinct.
Return names sorted by height in descending order.
Example 1
Input: names = ["Ayaan","Mira","Kai"], heights = [180,165,172]
Output: ["Ayaan","Kai","Mira"]
Explanation: 180 > 172 > 165.
Example 2
Input: names = ["Riya","Dev"], heights = [150,190]
Output: ["Dev","Riya"]
Example 3
Input: names = ["Sol"], heights = [161]
Output: ["Sol"]
Constraints
1 <= names.length <= 1000names.length == heights.length1 <= heights[i] <= 100000All values in heights are distinct.
Hints for Sort the People
Hint 1
Sorting the names alone loses the link to their heights.
Hint 2
Sort the indices by height instead, then read the names off in that order.
Hint 3
Descending means the comparator subtracts the other way round.
How to solve Sort the People
The two arrays are parallel, so sort a list of indices by the height they point at, then project the names through that order. Nothing needs to be paired up into objects.
Approach
- Build
order = [0, 1, …, n-1]. - Sort
orderwith the comparatorheights[b] - heights[a], which puts the tallest first. - Map
orderback throughnamesto build the result.
Why it works
Sorting indices keeps the association between a name and its height intact for free, because the index is the association. Distinct heights mean the comparator is a strict total order, so the result is unique.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Sorting
heightsandnamesseparately destroys the pairing. heights[a] - heights[b]sorts ascending — the shortest person would lead.
Reference solution
Python
from typing import List
def sortPeople(names: List[str], heights: List[int]) -> List[str]:
order = sorted(range(len(names)), key=lambda i: -heights[i])
return [names[i] for i in order]Java
public static String[] sortPeople(String[] names, int[] heights) {
int n = names.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Integer.compare(heights[b], heights[a]));
String[] out = new String[n];
for (int i = 0; i < n; i++) out[i] = names[order[i]];
return out;
}C++
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
int n = (int) names.size();
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return heights[a] > heights[b]; });
vector<string> out;
for (int i = 0; i < n; i++) out.push_back(names[order[i]]);
return out;
}JavaScript
var sortPeople = function(names, heights) {
var order = [];
for (var t = 0; t < names.length; t++) order.push(t);
order.sort(function(a, b) { return heights[b] - heights[a]; });
var out = [];
for (var i = 0; i < order.length; i++) out.push(names[order[i]]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets