NeetCode #149LC-2191MediumArrays & Hashing
← Back to All Problems#149 · #2191 · Sort the Jumbled Numbers(将杂乱数组排序)
📌 Problem Statement & Constraints
You are given a 0-indexed integer array
nums and an array mapping of 10 digits. The mapped value of a number is obtained by replacing each digit d with mapping[d]. Sort nums by mapped value ascending, breaking ties by the original index. Constraints: 1 <= nums.length <= 3 * 10^4, 0 <= nums[i] < 10^9, mapping.length == 10.💡 Core Algorithmic Approaches
- Compute the mapped value for each number once, then sort the indices by
(mapped_value, original_index). - The mapped value is built by processing the digits in order and appending
mapping[digit]. - Sorting indices rather than the values themselves preserves the original element for the output.
- Ties must be broken by the original index, which a stable sort would also achieve -- but stating the index in the key is explicit and safe.
💻 Benchmark Python3 Implementation
class Solution:
def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
def mapped(x: int) -> int:
return int("".join(str(mapping[int(d)]) for d in str(x)))
order = sorted(range(len(nums)), key=lambda i: (mapped(nums[i]), i))
return [nums[i] for i in order]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * L log n) where L is the number of digits: each comparison needs the mapped value, so precomputing it (as the key function does, once per element) keeps this at O(n * L + n log n).
💾 Space Complexity
O(n) for the index list and the sort's internal storage.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the tie-break on the original index: the problem requires ties to preserve the original order.
- Leading zeros in the mapped value:
mappingmay map a digit to 0, andint()drops leading zeros, which is correct -- the mapped value is a number, not a string. - Recomputing the mapped value inside a comparator: O(n log n * L) instead of O(n * L); use a
keyfunction so each value is computed once. - Sorting the numbers themselves: you would lose the ability to break ties by the original index unless you carry it along.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.