⚡Flashcard Drill➔
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

  1. Compute the mapped value for each number once, then sort the indices by (mapped_value, original_index).
  2. The mapped value is built by processing the digits in order and appending mapping[digit].
  3. Sorting indices rather than the values themselves preserves the original element for the output.
  4. 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: mapping may map a digit to 0, and int() 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 key function 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems