Sort the People — LeetCode #2418 (Easy)
Tags: Array, Hash Table, String, Sorting
Related patterns: Sorting, Array
Brute Force approach
Time complexity: O(n²). Space complexity: O(1).
The brute-force approach involves repeatedly finding the tallest person and placing them in the correct position. This is akin to sorting a deck of cards by repeatedly finding the highest card and moving it to the front.
This complexity arises because for each person, we may need to look through all remaining people to find the tallest, leading to a nested loop.
- Step 1: Create a loop that runs for each index in the heights array.
- Step 2: In each iteration, find the index of the maximum height in the remaining unsorted portion of the array.
- Step 3: Swap the found maximum height with the height at the current index, and do the same for the names array.
1. Initial: names = ["Mary", "John", "Emma"], heights = [180, 165, 170]
2. i = 0: max_index = 0 (180), swap with index 0 (no change)
3. i = 1: max_index = 1 (165), find max at index 2 (170), swap: names = ["Mary", "Emma", "John"], heights = [180, 170, 165]
4. i = 2: max_index = 2 (165), swap with index 2 (no change)
5. Result: names = ["Mary", "Emma", "John"]
Optimal Solution approach
Time complexity: O(n log n). Space complexity: O(n).
The optimal solution leverages sorting to efficiently arrange names based on heights. This is like organizing a list of books by height using a library's sorting system.
This complexity is due to the sorting step, which is more efficient than the nested loops used in the brute-force approach.
- Step 1: Create a list of tuples pairing each name with its corresponding height.
- Step 2: Sort this list of tuples based on the height in descending order.
- Step 3: Extract the names from the sorted list and return them.
1. Initial: names = ["Mary", "John", "Emma"], heights = [180, 165, 170]
2. Create pairs: [(180, "Mary"), (165, "John"), (170, "Emma")]
3. Sort pairs: [(180, "Mary"), (170, "Emma"), (165, "John")]
4. Extract names: ["Mary", "Emma", "John"]
Key Insights
- Sorting can drastically reduce the complexity of the problem compared to finding maximums repeatedly.
- Using data structures like tuples or pairs can simplify the association between names and heights.
Common Mistakes
- Not considering the need to maintain the association between names and heights when sorting.
- Overlooking the fact that heights are distinct, which simplifies the sorting process.
Interview Tips
- Always clarify the problem requirements and constraints before jumping into coding.
- Think about the efficiency of your approach and be prepared to discuss trade-offs.
- Practice explaining your thought process as you code, as this can help you catch mistakes early.
