💬 Discord
Sign In
NeetCode #95LC-2418EasyArrays & Hashing
← Back to All Problems

#95 · #2418 · Sort the People(按身高排序)

📌 Problem Statement & Constraints

Given arrays names and heights (aligned by index), return names sorted in descending order of heights. Constraints: 1 <= names.length == heights.length <= 1000; all heights are distinct.

💡 Core Algorithmic Approaches

  1. Pair each name with its height, sort the pairs by height descending, then extract the names.
  2. Sorting indices rather than zipped tuples avoids the trap of the reverse sort also reversing equal names -- though heights are distinct here, so it would not bite.
  3. The index-based approach is the safest idiom when only one field should drive the order.
  4. This is a two-line problem whose only real content is getting the sort direction right.

💻 Benchmark Python3 Implementation

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        order = sorted(range(len(names)), key=lambda i: -heights[i])
        return [names[i] for i in order]


# Zip-based variant (safe here because heights are distinct)
class Solution2:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        return [n for _, n in sorted(zip(heights, names), reverse=True)]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(n) for the index list and the result.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting ascending: the problem asks for descending order of heights.
  • Using sorted(zip(names, heights), reverse=True): the tuple comparison would break ties on the name in reverse order, which is usually not intended. Put the sort key first in the tuple, or sort by index.
  • Assuming names are unique: only the heights are guaranteed distinct.