2418. Sort the People

EasyView on LeetCode

Array Hash Table String Sorting

Time: O(n log n)

Space: O(n)

Problem Overview

Each name is paired with a height.

Intuition

Each name is paired with a height. Sort by height in descending order and return the names in that order — the tallest person first. This is standard sort-by-key with a custom comparator on the height field while preserving name association.

Algorithm

1Build pairs (name[i], height[i]) for each index.
2Sort pairs by height descending (taller first).
3Extract the name from each pair in sorted order into the result array.
4Return the reordered names.

Example Walkthrough

Input: names = ["Mary","John","Emma"], heights = [180,165,170]

1.Pairs: (Mary,180), (John,165), (Emma,170).
2.Sort by height: Mary 180, Emma 170, John 165.

Output: ["Mary","Emma","John"]

Common Pitfalls

•Sort pairs together — never sort heights and names independently.
•Stable sort is not required but names must stay matched to heights.
•Equal heights: any order among ties is usually acceptable.

2418.cs

// Approach: Pair (height, name) and sort by height descending; extract names.
// Time: O(n log n) Space: O(n)

public class Solution
{
    public string[] SortPeople(string[] names, int[] heights)
    {
        List<KeyValuePair<int, string>> heightAndNames = new List<KeyValuePair<int, string>>();

        for (int i = 0; i < names.Length; ++i)
            heightAndNames.Add(new KeyValuePair<int, string>(heights[i], names[i]));

        heightAndNames.Sort((a, b) => b.Key.CompareTo(a.Key));

        for (int i = 0; i < heightAndNames.Count; ++i)
            names[i] = heightAndNames[i].Value;

        return names;
    }
}

Was this solution helpful?