Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Sort the People solution and explanation

EasyArrayHash TableSortingString5 min read84.9% acceptanceUpdated 9 Apr 2026
Asked atInfosysMicrosoftAmazonGoogleMetaBloomberg
Practise Sort the People
6:09
Sort the People - Leetcode 2418 - PythonNeetCodeIO · 6:09 · 7K viewsWatch on YouTube
9 more videos on this problem
  1. Sort the People - Leetcode 2418 - PythonNeetCodeIO · 6:09 · 7K views
  2. LeetCode 2418. Sort the People | Interview Preparation | English | code iocode io - English · 11:37 · 1K views
  3. 2418. Sort the People (Leetcode Easy)Programming Live with Larry · 2:53 · 1K views
  4. SORT THE PEOPLE (LEETCODE 2418 ) SOLUTION IN JAVA | 2418 | LEETCODE | SOLUTION |Economic Coder · 11:38 · 1K views
  5. Leetcode 2418 Sort the People | Codinng Decoded SDE SheetCoding Decoded · 2:52 · 1K views
  6. LeetCode 2418 : Sort the People | Solution in JAVAAmit Manjarly · 10:03 · 563 views
  7. Leetcode 2418. Sort the People [SOLUTION]Elite Code · 8:33 · 322 views
  8. LeetCode 2418 : Sort the People | Solution in C++Amit Manjarly · 8:52 · 217 views
  9. Leetcode Poblem 2418. Sort the People.Solution with python.Codium · 3:09 · 167 views
  10. 2418. Sort the People - Leetcode - Hashmap- C++ Tutorialcodetutorial4you · 8:06 · 122 views

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

Approach overview

Problem Overview: You receive two arrays: names and heights. Each index represents a person. The task is to return the names sorted in descending order of height while keeping the correct name-height association.

This problem is essentially a sorting task with linked data. The key constraint is preserving the relationship between each name and its height while ordering by height. Most solutions rely on combining or referencing indices so the pairing is never lost during sorting.

Approach 1: Pairing and Sorting (Time: O(n log n), Space: O(n))

Create pairs that keep each person's name tied to their height. For example, combine them as (height, name) tuples or objects. Once paired, sort the list by height in descending order using a standard sorting algorithm. After sorting, iterate through the pairs and extract the names into the result array.

The key insight is that pairing eliminates the risk of losing the relationship between the two arrays during sorting. This approach is straightforward and maps directly to built‑in sort utilities available in most languages. It relies on concepts from array manipulation and sorting. Because the entire list is sorted, the complexity is dominated by the sorting step.

Approach 2: Directly Sorting Indices (Time: O(n log n), Space: O(n))

Instead of pairing values, create an index array containing 0..n-1. Sort this index array based on the values in the heights array, ordering indices so that taller heights appear first. Once sorted, iterate through the index list and pick the corresponding names from the names array.

This approach keeps the original arrays untouched and only reorders indices. The technique is common when working with parallel arrays and avoids allocating pair objects. It still performs a comparison-based sort, so the time complexity remains O(n log n). The idea frequently appears in problems involving array indexing and comparator-based sorting.

Recommended for interviews: Pairing and sorting is the most direct and readable solution, which makes it the expected answer in many interviews. Sorting indices demonstrates deeper control over memory layout and array manipulation, which can be useful when dealing with large datasets or immutable structures. Showing both approaches signals strong understanding of how to maintain relationships between multiple arrays during sorting.

Approach 1: Approach 1: Pairing and Sorting

This approach involves pairing each name with its corresponding height, sorting these pairs by height in descending order, and then extracting the sorted names. This makes use of the association between each name and its corresponding height.

def sort_people(names, heights):
    paired_list = list(zip(heights, names))
    paired_list.sort(reverse=True, key=lambda x: x[0])
    sorted_names = [name for _, name in paired_list]
    return sorted_names
import java.util.*;

public class SortPeople {
    public static 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]);
        }
        Arrays.sort(people, (a, b) -> b.height - a.height);
        String[] sortedNames = new String[n];
        for (int i = 0; i < n; i++) {
            sortedNames[i] = people[i].name;
        }
        return sortedNames;
    }

    static class Person {
        String name;
        int height;

        Person(String name, int height) {
            this.name = name;
            this.height = height;
        }
    }
}
#include <vector>
#include <string>
#include <algorithm>

std::vector<std::string> sortPeople(std::vector<std::string>& names, std::vector<int>& heights) {
    std::vector<std::pair<int, std::string>> people;
    int n = names.size();
    for (int i = 0; i < n; ++i) {
        people.push_back({heights[i], names[i]});
    }
    std::sort(people.begin(), people.end(), std::greater<>());
    std::vector<std::string> sortedNames(n);
    for (int i = 0; i < n; ++i) {
        sortedNames[i] = people[i].second;
    }
    return sortedNames;
}
function sortPeople(names, heights) {
    const people = names.map((name, index) => ({ name, height: heights[index] }));
    people.sort((a, b) => b.height - a.height);
    return people.map(person => person.name);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char* name;
    int height;
} Person;

int comparePersons(const void* a, const void* b) {
    return ((Person*)b)->height - ((Person*)a)->height;
}

void sortPeople(char** names, int* heights, int n, char** sortedNames) {
    Person* people = malloc(n * sizeof(Person));
    for (int i = 0; i < n; ++i) {
        people[i].name = names[i];
        people[i].height = heights[i];
    }
    qsort(people, n, sizeof(Person), comparePersons);
    for (int i = 0; i < n; ++i) {
        sortedNames[i] = people[i].name;
    }
    free(people);
}
using System;
using System.Linq;

public class SortPeopleClass {
    public static string[] SortPeople(string[] names, int[] heights) {
        var people = names.Zip(heights, (name, height) => new { Name = name, Height = height });
        return people.OrderByDescending(p => p.Height).Select(p => p.Name).ToArray();
    }
}

The code creates a list of tuples, each containing a height and the corresponding name. The list is then sorted in descending order based on the height, by using a lambda function as the sorting key. Finally, the sorted names are extracted from the tuples.

Complexity

Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(n) for storing the list of tuples.

Try this approach in the editor

Approach 2: Approach 2: Directly Sorting Indices

Rather than pairing names and heights, you can directly sort the indices of the height array. After sorting the indices by descending heights, you can retrieve the names based on this sorted order of heights.

def sort_people(names, heights):
    index_sorted_by_height = sorted(range(len(heights)), key=lambda i: -heights[i])
    return [names[i] for i in index_sorted_by_height]
import java.util.*;

public class SortPeopleByIndex {
    public static String[] sortPeople(String[] names, int[] heights) {
        Integer[] indices = new Integer[names.length];
        for (int i = 0; i < names.length; i++) {
            indices[i] = i;
        }
        Arrays.sort(indices, (a, b) -> Integer.compare(heights[b], heights[a]));
        // Prepare sorted names based on sorted indices
        String[] result = new String[names.length];
        for (int i = 0; i < indices.length; i++) {
            result[i] = names[indices[i]];
        }
        return result;
    }
}
#include <vector>
#include <string>
#include <algorithm>

std::vector<std::string> sortPeopleByIndex(std::vector<std::string>& names, std::vector<int>& heights) {
    int n = names.size();
    std::vector<int> indices(n);
    for (int i = 0; i < n; ++i) {
        indices[i] = i;
    }
    std::sort(indices.begin(), indices.end(), [&](int a, int b) { return heights[a] > heights[b]; });
    std::vector<std::string> result(n);
    for (int i = 0; i < n; ++i) {
        result[i] = names[indices[i]];
    }
    return result;
}
function sortPeople(names, heights) {
    const indices = Array.from({ length: heights.length }, (_, i) => i);
    indices.sort((a, b) => heights[b] - heights[a]);
    return indices.map(index => names[index]);
}
#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b, void* data) {
    const int* indices = data;
    int idx_a = *(const int*)a;
    int idx_b = *(const int*)b;
    int* heights = (int*)data;
    return heights[idx_b] - heights[idx_a];
}

void sortPeople(char** names, int* heights, int n, char** sortedNames) {
    int* indices = malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i) {
        indices[i] = i;
    }
    qsort_r(indices, n, sizeof(int), cmp, heights);
    for (int i = 0; i < n; ++i) {
        sortedNames[i] = names[indices[i]];
    }
    free(indices);
}
using System;
using System.Linq;

public class SortPeopleByIndexClass {
    public static string[] SortPeople(string[] names, int[] heights) {
        int[] indices = Enumerable.Range(0, names.Length).ToArray();
        Array.Sort(indices, (a, b) => heights[b].CompareTo(heights[a]));
        return indices.Select(i => names[i]).ToArray();
    }
}

The code sorts indices based on the heights using negative heights to direct the sorting to descending order. After sorting, use these indices to create the sorted list of names.

Complexity

Time Complexity: O(n log n) due to sorting the indices.
Space Complexity: O(n) for auxiliary storage of indices.

Try this approach in the editor

Approach 3: Sorting

According to the problem description, we can create an index array idx of length n, where idx[i]=i. Then we sort each index in idx in descending order according to the corresponding height in heights. Finally, we traverse each index i in the sorted idx and add names[i] to the answer array.

We can also create an array arr of length n, where each element is a tuple (heights[i], i). Then we sort arr in descending order by height. Finally, we traverse each element (heights[i], i) in the sorted arr and add names[i] to the answer array.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the arrays names and heights.

function sortPeople(names: string[], heights: number[]): string[] {
    const n = names.length;
    const idx = new Array(n);
    for (let i = 0; i < n; ++i) {
        idx[i] = i;
    }
    idx.sort((i, j) => heights[j] - heights[i]);
    const ans: string[] = [];
    for (const i of idx) {
        ans.push(names[i]);
    }
    return ans;
}
func sortPeople(names []string, heights []int) (ans []string) {
	n := len(names)
	idx := make([]int, n)
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(i, j int) bool { return heights[idx[j]] < heights[idx[i]] })
	for _, i := range idx {
		ans = append(ans, names[i])
	}
	return
}
impl Solution {
    pub fn sort_people(names: Vec<String>, heights: Vec<i32>) -> Vec<String> {
        let mut combine: Vec<(String, i32)> = names.into_iter().zip(heights.into_iter()).collect();
        combine.sort_by(|a, b| b.1.cmp(&a.1));
        combine.iter().map(|s| s.0.clone()).collect()
    }
}
Try this approach in the editor

Approach 4: Default Approach

function sortPeople(names: string[], heights: number[]): string[] {
    return names
        .map<[string, number]>((s, i) => [s, heights[i]])
        .sort((a, b) => b[1] - a[1])
        .map(([v]) => v);
}
func sortPeople(names []string, heights []int) []string {
	n := len(names)
	arr := make([][2]int, n)
	for i, h := range heights {
		arr[i] = [2]int{h, i}
	}
	sort.Slice(arr, func(i, j int) bool { return arr[i][0] > arr[j][0] })
	ans := make([]string, n)
	for i, x := range arr {
		ans[i] = names[x[1]]
	}
	return ans
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Pairing and Sorting

Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(n) for storing the list of tuples.

Approach 2: Directly Sorting Indices

Time Complexity: O(n log n) due to sorting the indices.
Space Complexity: O(n) for auxiliary storage of indices.

Sorting–
Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Pairing and SortingO(n log n)O(n)Most common and readable approach; ideal when using built-in sort with paired values.
Directly Sorting IndicesO(n log n)O(n)Useful when you want to avoid modifying the original arrays and only reorder references.

Frequently asked questions

Is Sort the People easy or hard?

Sort the People is classified as an Easy problem. The main idea is recognizing that you must sort while preserving the mapping between names and heights. Once that relationship is maintained, the implementation becomes straightforward.

Sort the People Python/Java solution

In Python, you can combine heights and names using zip and sort by height in descending order. In Java, create pairs or sort indices using a custom comparator referencing the heights array. Both implementations run in O(n log n) time.

How to solve Sort the People in O(n)?

An O(n) solution is generally not possible because the output requires ordering elements by value, which typically requires comparison-based sorting. Standard solutions rely on sorting heights, resulting in O(n log n) time complexity.

What is the best approach for Sort the People?

The most common solution pairs each name with its height and sorts the pairs in descending order of height. This keeps the relationship between the two arrays intact and uses a standard sort operation. The time complexity is O(n log n) and space complexity is O(n).

Is Sort the People asked at Google/Amazon/Meta?

Problems involving sorting paired data and maintaining relationships between arrays appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the pattern of sorting based on a key while preserving associated values is common.

What data structure is used in Sort the People?

The solution typically uses arrays along with either paired tuples or an index array. Sorting with a custom comparator is the main technique, making it a classic array and sorting problem.

What is the time complexity of Sort the People?

The dominant step is sorting the people by height. Comparison-based sorting requires O(n log n) time for n people. Space complexity is typically O(n) if pairs or index arrays are created during the process.

Comments

Next problem · similarSort Array by Increasing FrequencyEasy
Now write it yourselfClose this page and solve Sort the People in the editor, without looking.
Practise Sort the People