To solve Sort the People, map each name to its corresponding height, then sort pairs by height descending. Use array scanning to track the tallest remaining person for each position, ensuring correctness. This approach leverages the distinct heights and direct hash lookup to avoid mistakes in ordering while maintaining O(n log n) performance.
Problem Statement
Given two arrays of equal length, names and heights, where names[i] is a string representing the name of the ith person and heights[i] is a distinct positive integer representing that person's height, return an array of names sorted from tallest to shortest. The arrays are guaranteed to have the same length n and each height is unique.
You must maintain the correct name-to-height mapping when sorting. For example, if the tallest person is at index 2, their name should appear first in the output. This requires scanning through the arrays and performing swaps or mapping lookups to reorder names efficiently according to the descending heights.
Examples
Example 1
Input: names = ["Mary","John","Emma"], heights = [180,165,170]
Output: ["Mary","Emma","John"]
Mary is the tallest, followed by Emma and John.
Example 2
Input: names = ["Alice","Bob","Bob"], heights = [155,185,150]
Output: ["Bob","Alice","Bob"]
The first Bob is the tallest, followed by Alice and the second Bob.
Constraints
- n == names.length == heights.length
- 1 <= n <= 103
- 1 <= names[i].length <= 20
- 1 <= heights[i] <= 105
- names[i] consists of lower and upper case English letters.
- All the values of heights are distinct.
Solution Approach
Pair Names with Heights
Create an array of tuples where each tuple contains a height and its corresponding name. This ensures that the mapping between names and heights remains intact during sorting.
Sort by Height Descending
Use the built-in sort function or any comparison-based sort on the array of tuples, sorting by the height value in descending order. This leverages the array scanning plus hash lookup pattern to correctly order names.
Extract Sorted Names
After sorting, iterate through the array of tuples and collect the names in order. This step returns the final array of names sorted from tallest to shortest while preserving their original associations.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n \cdot \log n) |
| Space | O(n) |
Time complexity is O(n \cdot \log n) due to the sorting of n elements. Space complexity is O(n) because we create an auxiliary array of tuples pairing names and heights.
What Interviewers Usually Probe
- Expect a direct mapping of names to heights and correct descending sort order.
- Be prepared to explain why a hash or tuple-based approach avoids mixing names and heights.
- Highlight the pattern of scanning arrays and using auxiliary structures for sorting without losing associations.
Common Pitfalls or Variants
Common pitfalls
- Sorting names and heights separately without pairing can misalign names with heights.
- Assuming heights are not distinct and trying to handle duplicates unnecessarily.
- Forgetting to return only names in the final output instead of height-name pairs.
Follow-up variants
- Sort by other attributes such as weight or age while keeping name mapping intact.
- Handle duplicate heights by breaking ties alphabetically or by original index.
- Sort names in ascending height order instead of descending.
How GhostInterview Helps
- GhostInterview highlights the need to maintain correct name-height pairs using array scanning and hash lookup.
- It provides step-by-step guidance to implement sorting without losing original mappings, ensuring correct output.
- The solver detects common mistakes like misaligned arrays and explains why the tuple approach fixes ordering failures.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the most efficient way to solve Sort the People?
Pair each name with its height, sort the pairs by height descending using array scanning and hash lookup, then extract names.
Can I sort names and heights separately?
No, sorting separately breaks the association between names and heights, leading to incorrect output.
Does this problem work with duplicate heights?
The original constraints guarantee distinct heights, so handling duplicates is unnecessary unless the variant specifies it.
What data structure ensures name-height mapping is preserved during sort?
Using tuples or pairs of (height, name) maintains the mapping and allows safe sorting by height.
How does array scanning plus hash lookup help in Sort the People?
It allows finding the tallest remaining person efficiently at each step and swapping or reordering names without losing associations.
Need direct help with Sort the People instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Sort the People from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Identify the most popular video creator by summing views and selecting their top-viewed video with array and hash patterns.
Open problem page#2512 Reward Top K StudentsCalculate top K student scores by scanning reports and using hash tables for positive and negative word lookups efficiently.
Open problem page#2273 Find Resultant Array After Removing AnagramsThis problem requires removing adjacent anagrams from a list of words using an array scanning and hash lookup approach.
Open problem page