Sort the People — Easy Problem & Solution

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 <= 1000
• names.length == heights.length
• 1 <= heights[i] <= 100000
• All values in heights are distinct.

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

1. Build order = [0, 1, …, n-1].
2. Sort order with the comparator heights[b] - heights[a], which puts the tallest first.
3. Map order back through names to 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 heights and names separately 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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy