Sort the People

Easy
625.

Sort the People

Sort the People is an easy coding problem on arrays, hash table and sorting, asked in Amazon, TCS and Infosys interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} names
 * @param {number[]} heights
 * @return {string[]}
 */
var sortPeople = function(names, heights) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Sort the People

  1. Hint 1

    Sorting the names alone loses the link to their heights.

  2. Hint 2

    Sort the indices by height instead, then read the names off in that order.

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

  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]

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