2191. Sort the Jumbled Numbers - Explanation

1. Convert To Strings + Sorting

Intuition

We need to sort numbers based on their "mapped" values, where each digit is replaced according to a mapping array. By converting each number to a string, we can easily iterate through its digits and build the mapped value. We store each mapped value along with the original index to preserve relative ordering for equal mapped values, then sort by the mapped values.

Algorithm

For each number in the input array, convert it to a string.
Build the mapped value by iterating through each character, looking up its mapped digit, and constructing the new number.
Store pairs of (mapped value, original index) for each number.
Sort the pairs by mapped value. Since the sort is stable, equal mapped values will maintain their original relative order.
Construct the result array by extracting the original numbers using the stored indices.

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        pairs = []

        for i, n in enumerate(nums):
            n = str(n)
            mapped_n = 0
            for c in n:
                mapped_n *= 10
                mapped_n += mapping[int(c)]
            pairs.append((mapped_n, i))

        pairs.sort()
        return [nums[p[1]] for p in pairs]

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Iterate On Numbers + Sorting

Intuition

Instead of converting numbers to strings, we can extract digits directly using arithmetic operations. We repeatedly take the last digit using modulo, map it, and accumulate the mapped value by multiplying by the appropriate power of 10. This avoids the overhead of string conversion while achieving the same result.

Algorithm

For each number, initialize a mapped value of 0 and a base multiplier of 1.
Handle the special case where the number is 0 by directly using the mapped value of digit 0.
Otherwise, repeatedly extract the last digit using modulo 10, map it, multiply by the current base, and add to the mapped value. Then divide the number by 10 and multiply the base by 10.
Store pairs of (mapped value, original index).
Sort pairs by mapped value and construct the result using the stored indices.

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        pairs = []

        for i, n in enumerate(nums):
            mapped_n = 0
            base = 1

            if n == 0:
                mapped_n = mapping[0]
            else:
                while n > 0:
                    digit = n % 10
                    n //= 10
                    mapped_n += base * mapping[digit]
                    base *= 10

            pairs.append((mapped_n, i))

        pairs.sort()
        return [nums[p[1]] for p in pairs]

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

Common Pitfalls

Not Handling Zero as a Special Case

When using arithmetic to extract digits, the number zero requires special handling. The while loop while (n > 0) never executes for zero, leaving the mapped value uninitialized. You must explicitly handle n == 0 by directly using mapping[0].

Using an Unstable Sort Without Preserving Original Order

The problem requires that elements with equal mapped values maintain their original relative order. Using an unstable sort without tracking original indices will produce incorrect results when multiple numbers map to the same value.

Integer Overflow When Building Mapped Values

For very large numbers, the mapped value can potentially overflow. While this is less common in languages with arbitrary precision integers like Python, in languages like Java or C++ you should be aware of the maximum input constraints to ensure the mapped value fits within the integer type.