2418. Sort the People

EasyArrayHash TableStringSorting
Leetcode Link

Problem Description

In this problem, we are given two arrays: names and heights. Both arrays have the same length, n, and for any given index i, names[i] represents the name of a person, and heights[i] represents their respective height. The heights array is made up of distinct positive integers, which means no two people can have the same height.

Our task is to sort the people by their heights in descending order, i.e., from the tallest to the shortest person. The output should be a reordered names array that reflects this sorting by height.

Understanding the problem involves recognizing that we need to maintain the association between each person's name and their height while sorting, which is commonly known as a "sort by keys" problem where the heights serve as keys, and the names are the values associated with those keys.

Intuition

The solution to this problem requires a sorting strategy. Since each person's height is unique (there are no duplicates), we can sort the people based on their heights in descending order. However, rather than sorting heights directly, we need to sort indices that can then be used to reorder the names.

Here's the intuitive breakdown of the solution:

  1. Generate a list of indices idx from 0 to n-1 where n is the length of the heights array.
  2. Sort the idx list, but instead of sorting it in the usual ascending order, we use a custom sorting key. The key is a function that takes an index i and returns the negative of heights[i]. By using the negative value, we effectively sort the indices in order of descending heights since the usual sorting is in ascending order.
  3. After sorting the indices in this way, we can create a new list with names in the proper order. We do this by iterating through the sorted idx list and fetching the corresponding name from the names list for each sorted index.

This approach allows us to sort the names list according to the descending order of the heights without losing the association between names and their corresponding heights.

Learn more about Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The implementation of the solution involves a few key steps, and it employs basic list manipulation and sorting techniques in Python. Here's a step-by-step walkthrough of the algorithm and patterns used:

  1. Initialization of index list: We create a list called idx which contains indices from 0 to n-1, where n is the length of the heights array. This is accomplished with the range function in Python, which returns a sequence of numbers. We convert it to a list using the built-in list function.

    1idx = list(range(len(heights)))

  2. Custom Sorting: We want to sort the indices based on the values in heights array but in descending order. To do this, we use the sort method of the list. The sort method is modified by a custom key function, which is passed as a lambda function. The lambda function takes each index i and returns -heights[i], which ensures that we are sorting in descending order based on height values.

    1idx.sort(key=lambda i: -heights[i])

  3. Reordering names by sorted indices: With the indices sorted in the correct order, the final step is to reorder the names according to these indices. We accomplish this by iterating over the idx and using a list comprehension to create a new list. For each i in idx, we fetch names[i] and add it to the new list.

    1return [names[i] for i in idx]

This approach leverages a key aspect of Python's sorting capabilities, where sort is stable and can be customized easily with a key function. By inverting the heights in the key function (using negative heights), we avoid the need to write a custom comparison function; the sort method automatically handles it for us.

This solution is efficient because it does not involve any complicated data structures or algorithms beyond basic list operations and sorting, and it maintains a time complexity of O(n log n), where n is the number of people in the list. The custom key function does not significantly affect this complexity, as it simply changes the values used for comparison during the sort process.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following lists of names and heights:

1names = ['Alice', 'Bob', 'Charlie', 'Dana']
2heights = [155, 165, 160, 170]

We can see that Dana is the tallest, followed by Bob, then Charlie, and finally Alice. We want to sort the names array so that it matches the descending order of heights. Following the steps in the solution approach:

  1. Initialization of index list: We create a list of indices which will correspond to the indices of the heights list.

    1idx = list(range(len(heights)))  # idx will be [0, 1, 2, 3]

  2. Custom Sorting: Now we sort idx by the heights in descending order by using the negative heights as the key for sorting.

    1idx.sort(key=lambda i: -heights[i])  # After sorting, idx will be [3, 1, 2, 0]

    The index 3 comes first as heights[3] (which is 170) is the greatest, and so on.

  3. Reordering names by sorted indices: Using our sorted idx, we reorder names by mapping each index to the corresponding name.

    1sorted_names = [names[i] for i in idx]  # This gives us ['Dana', 'Bob', 'Charlie', 'Alice']

Now, when we look at sorted_names, we have the names ordered by descending height:

1print(sorted_names)  # Output: ['Dana', 'Bob', 'Charlie', 'Alice']

This matches our expectations based on the heights. The sorted_names list is the resultant list where the corresponding names are ordered from the tallest to the shortest person. This example clearly demonstrates the efficacy of the solution approach for the problem described.

Solution Implementation

1from typing import List
2
3class Solution:
4    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
5        # This method sorts the people based on descending order of their heights. 
6        # It then returns a list of names of the people sorted by their heights.
7
8        # Generate an index list that matches the indexes of the heights list.
9        indices = list(range(len(heights)))
10
11        # Sort the indices list based on descending values of heights.
12        # The lambda function returns the negated height value for each index, sorting in descending order.
13        indices.sort(key=lambda i: -heights[i])
14
15        # Map the sorted indices to their corresponding names.
16        # This results in a list of names ordered by descending height.
17        sorted_names = [names[i] for i in indices]
18
19        # Return the list of sorted names.
20        return sorted_names
21
22# Example usage:
23# If we have two lists, one of names and one of the corresponding heights:
24# names = ["Mary", "John", "Emma"]
25# heights = [160, 180, 165]
26# solution = Solution()
27# sorted_people = solution.sortPeople(names, heights)
28# The output will be: ["John", "Emma", "Mary"]
29
1import java.util.Arrays;
2
3class Solution {
4    public String[] sortPeople(String[] names, int[] heights) {
5        // Extract the number of elements from the names array, which also applies to the heights array.
6        int numberOfPeople = names.length;
7
8        // Create an array of indices representing each person.
9        Integer[] indices = new Integer[numberOfPeople];
10
11        // Initialize the indices array with values from 0 to numberOfPeople - 1.
12        for (int i = 0; i < numberOfPeople; ++i) {
13            indices[i] = i;
14        }
15
16        // Sort the indices array based on the descending order of heights using a custom comparator.
17        // The comparator computes the difference between the heights at indices j and i.
18        Arrays.sort(indices, (i, j) -> heights[j] - heights[i]);
19
20        // Create a result array to store the sorted names based on the heights.
21        String[] sortedNames = new String[numberOfPeople];
22
23        // Build the result array by mapping sorted indices to their respective names.
24        for (int i = 0; i < numberOfPeople; ++i) {
25            sortedNames[i] = names[indices[i]];
26        }
27
28        // Return the array of names sorted by descending heights.
29        return sortedNames;
30    }
31}
32
1#include <algorithm> // include the algorithm header for std::sort and std::iota functions
2#include <numeric>   // include the numeric header for std::iota function
3#include <string>    // include the string header for using std::string
4#include <vector>    // include the vector header for using std::vector
5
6class Solution {
7public:
8    // This function sorts people by their heights in descending order
9    // Arguments:
10    //   names - a vector of strings representing people's names
11    //   heights - a vector of integers representing corresponding people's heights
12    // Returns:
13    //   A vector of strings representing people's names sorted by their heights in descending order
14    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
15        int numPeople = names.size(); // get the number of people
16        vector<int> indices(numPeople); // create a vector to hold indices
17        iota(indices.begin(), indices.end(), 0); // fill the vector with consecutive numbers starting at 0
18
19        // Use sort function with custom comparator to sort the indices based on descending order of heights
20        sort(indices.begin(), indices.end(), [&](int i, int j) { 
21            return heights[i] > heights[j]; 
22        });
23      
24        vector<string> sortedNames; // create a vector to hold the sorted names
25        sortedNames.reserve(numPeople); // reserve space in the vector for numPeople elements
26
27        // Construct the sorted names vector based on the sorted indices
28        for (int index : indices) {
29            sortedNames.push_back(names[index]); // add name to the result vector in sorted order
30        }
31
32        return sortedNames; // return the sorted names
33    }
34};
35
1function sortPeople(names: string[], heights: number[]): string[] {
2    // Get the number of people from the length of the names array.
3    const numberOfPeople = names.length;
4    // Initialize an index array to keep track of original indices.
5    const indices = new Array(numberOfPeople);
6    // Fill the index array with indices from 0 to numberOfPeople - 1.
7    for (let i = 0; i < numberOfPeople; ++i) {
8        indices[i] = i;
9    }
10    // Sort the index array based on heights in descending order.
11    // The sort compares the heights at the indices and sorts the indices array.
12    indices.sort((index1, index2) => heights[index2] - heights[index1]);
13    // Initialize an array to store the sorted names.
14    const sortedNames: string[] = [];
15    // Iterate over the sorted indices and push the corresponding name
16    // into the sortedNames array.
17    for (const index of indices) {
18        sortedNames.push(names[index]);
19    }
20    // Return the array of sorted names.
21    return sortedNames;
22}
23
Not Sure What to Study? Take the 2-min Quiz：

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Time and Space Complexity

Time Complexity

The time complexity of the given code is primarily determined by the sorting operation. The sort method on the idx list is using a custom key, which is based on the values of the heights list. Sorting in Python is implemented with the Timsort algorithm, which has a time complexity of O(n log n) in the average and worst case, where n is the number of elements to be sorted.

In the given code, the list idx has a length equal to that of names and heights, so there will be n items to sort, where n represents the length of either names or heights.

Hence, the overall time complexity is O(n log n).

Space Complexity

The space complexity of this function can be analyzed by looking at the additional memory used by the program.

  1. The list idx is created which will hold n integers. This contributes O(n) space.
  2. The sorting operation may temporarily require additional space to hold elements when sorting, contributing an additional O(log n) space due to the recursion stack of Timsort.
  3. After sorting, a new list comprehension is used to generate the result list based on the sorted indices. This list will also be of length n, which means an additional O(n) space.

As the dominant term in space complexity is O(n) (the space used for storing indices and the final output list), we can conclude the overall space complexity of the given code is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?

Recommended Readings

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫