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.

Description Hints 1 Solution Video 6:09

2418. Sort the People

Easy84.9% acceptance6 companies

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.

Asked at 6 companies

Infosys Microsoft Amazon

Google Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Find the tallest person and swap with the first person, then find the second tallest person and swap with the second person, etc. Repeat until you fix all n people.

6:09

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution