Sort the Jumbled Numbers

How it works

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.

Steps

1. For each number, initialize a mapped value of 0 and a base multiplier of 1.
2. Handle the special case where the number is 0 by directly using the mapped value of digit 0.
3. 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.
4. Store pairs of (mapped value, original index).
5. Sort pairs by mapped value and construct the result using the stored indices.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

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.

from typing import List

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]

class Solution {
public:
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
        vector<pair<int, int>> pairs;

        for (int i = 0; i < nums.size(); i++) {
            int mapped_n = 0, base = 1;
            int num = nums[i];

            if (num == 0) {
                mapped_n = mapping[0];
            } else {
                while (num > 0) {
                    int digit = num % 10;
                    num /= 10;
                    mapped_n += base * mapping[digit];
                    base *= 10;
                }
            }

            pairs.push_back({mapped_n, i});
        }

        sort(pairs.begin(), pairs.end());

        vector<int> res;
        for (auto& p : pairs) {
            res.push_back(nums[p.second]);
        }

        return res;
    }
};