algoadvance

Leetcode 2418. Sort the People

Problem Statement

You are given an array of strings names, where each names[i] is the name of the i-th person. You are also given an array heights, where each heights[i] is the height of the i-th person.

Return names sorted in descending order by the people’s heights.

Clarifying Questions

  1. What is the relationship between names and heights?
    • Each element in names corresponds to the person at the same index in heights.
  2. Can the names or heights be duplicated?
    • Names can be duplicated, but heights should be unique as per the problem description.
  3. Are there any constraints on the size of the arrays?
    • The problem does not explicitly state constraints, but typically LeetCode problems have reasonable constraints such as the arrays not exceeding 10^4 elements.
  4. What should we return if both arrays are empty or have different lengths?
    • If the arrays are empty or have different lengths, it’s likely out of scope for a well-defined problem. However, normal prerequisites should ensure they are non-empty and have the same length.

Strategy

  1. Combine Names and Heights: Create pairs or tuples of names and corresponding heights.
  2. Sort the Combined List: Sort these pairs based on the heights in descending order.
  3. Extract Sorted Names: Extract the names from the sorted list of pairs.

Code

Here is a Java implementation of the solution strategy:

import java.util.*;

public class SortPeopleByHeight {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        List<Pair> peopleList = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            peopleList.add(new Pair(heights[i], names[i]));
        }
        
        // Sort the list by heights in descending order
        peopleList.sort((a, b) -> b.height - a.height);
        
        String[] sortedNames = new String[n];
        for (int i = 0; i < n; i++) {
            sortedNames[i] = peopleList.get(i).name;
        }
        
        return sortedNames;
    }
    
    class Pair {
        int height;
        String name;
        
        Pair(int height, String name) {
            this.height = height;
            this.name = name;
        }
    }
    
    // Example usage:
    public static void main(String[] args) {
        SortPeopleByHeight sorter = new SortPeopleByHeight();
        String[] names = {"Mary", "John", "Emma"};
        int[] heights = {180, 165, 170};
        System.out.println(Arrays.toString(sorter.sortPeople(names, heights)));  // Output: [Mary, Emma, John]
    }
}

Time Complexity

Thus, the overall time complexity of the solution is O(n log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI