Problem Description

You are given an array mapping of length 10, where mapping[i] represents the mapping of the digit i to a new digit. You are also given an integer array nums. Your task is to sort the array nums in ascending order, but using the following custom rule:

• For each number in nums, replace every digit d in the number with mapping[d] to form a new integer (leading zeros are allowed in the mapped number).
• Sort nums based on these mapped values. If two numbers have the same mapped value, maintain their original relative order (i.e., the sort should be stable).

Constraints:

• Each digit in nums can be mapped independently.
• There is only one valid output for each input.
• Do not reuse or alter elements outside of the mapping rules.

Thought Process

At first glance, this problem seems similar to a standard sorting problem. However, instead of sorting the numbers by their natural integer value, we must first convert each number by mapping its digits, then sort according to these new mapped values.

A brute-force approach would be to:

• For each number, manually convert it digit by digit using the mapping.
• Store both the original number and its mapped value.
• Sort based on the mapped value.

We should also consider edge cases, such as numbers with leading zeros after mapping, and ensure that the mapping of digits is handled correctly for each digit, even if the number is 0.

Solution Approach

Let's break down the steps to solve the problem:

1. Map Each Number:
   • For each number in nums, convert it to a string so we can process each digit.
   • For each digit, use mapping to determine its mapped value.
   • Concatenate the mapped digits to form the mapped number as a string, then convert it back to an integer.
2. Pair Original and Mapped Values:
   • For each number, store a tuple or object containing both the original number and its mapped value.
3. Sort by the Mapped Value:
   • Sort the list of pairs/objects by the mapped value.
   • Use a stable sort to maintain the original order for numbers with the same mapped value.
4. Return the Sorted Original Numbers:
   • After sorting, extract the original numbers in the new order.

We use a stable sort because the problem requires that numbers with the same mapped value retain their original order. Most built-in sort functions in modern languages (like Python's sorted and JavaScript's Array.prototype.sort) are stable, but it's important to confirm this for your language of choice.

Example Walkthrough

Input:
mapping = [2,1,4,8,6,3,0,9,7,5]
nums = [990, 332, 32]

1. Map Each Number:
   • 990: '9' → 5, '9' → 5, '0' → 2 ⇒ mapped: '552' ⇒ 552
   • 332: '3' → 8, '3' → 8, '2' → 4 ⇒ mapped: '884' ⇒ 884
   • 32: '3' → 8, '2' → 4 ⇒ mapped: '84' ⇒ 84
2. Pair Original and Mapped:
   • (990, 552)
   • (332, 884)
   • (32, 84)
3. Sort by Mapped Value:
   • (32, 84)
   • (990, 552)
   • (332, 884)
4. Return Sorted Originals:
   • [32, 990, 332]

Thus, the output is [32, 990, 332].

Time and Space Complexity

Brute-Force Approach:

• For every number, we would generate all possible mappings and try all permutations—this is unnecessary and inefficient for this problem.

• Let n be the number of elements in nums, and k be the maximum number of digits in any number.
• Mapping each number: O(n * k)
• Sorting: O(n log n)
• Extracting results: O(n)
• Total time complexity: O(nk + n log n)
• Space complexity: O(n) for storing pairs of original and mapped numbers.

The mapping step is fast because the number of digits (k) is small (at most 10 for 32-bit integers), so the overall complexity is dominated by the sorting step.

Summary

The key insight in this problem is to treat the digit mapping as a transformation step before sorting. By pairing each original number with its mapped value, we can leverage a stable sort to achieve the desired order efficiently. This approach is both simple and robust, making it easy to implement in any mainstream programming language. The solution's elegance lies in separating the mapping logic from the sorting logic, ensuring clarity and correctness.

Code Implementation

class Solution:
    def sortJumbled(self, mapping, nums):
        def mapped_value(num):
            return int(''.join(str(mapping[int(d)]) for d in str(num)))
        # Pair each number with its mapped value and original index for stability
        mapped_nums = [(mapped_value(num), idx, num) for idx, num in enumerate(nums)]
        mapped_nums.sort()
        return [num for _, _, num in mapped_nums]
      

class Solution {
public:
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
        vector<tuple<int, int, int>> mapped_nums;
        for (int i = 0; i < nums.size(); ++i) {
            int num = nums[i];
            if (num == 0) {
                mapped_nums.push_back({mapping[0], i, num});
                continue;
            }
            int mapped = 0, factor = 1;
            vector<int> digits;
            int temp = num;
            while (temp > 0) {
                digits.push_back(temp % 10);
                temp /= 10;
            }
            for (int j = digits.size() - 1; j >= 0; --j) {
                mapped = mapped * 10 + mapping[digits[j]];
            }
            mapped_nums.push_back({mapped, i, num});
        }
        sort(mapped_nums.begin(), mapped_nums.end());
        vector<int> result;
        for (auto& tup : mapped_nums) {
            result.push_back(get<2>(tup));
        }
        return result;
    }
};
      

import java.util.*;

class Solution {
    public int[] sortJumbled(int[] mapping, int[] nums) {
        int n = nums.length;
        int[][] mappedNums = new int[n][3]; // [mappedValue, originalIndex, originalNum]
        for (int i = 0; i < n; i++) {
            mappedNums[i][0] = getMapped(nums[i], mapping);
            mappedNums[i][1] = i;
            mappedNums[i][2] = nums[i];
        }
        Arrays.sort(mappedNums, (a, b) -> {
            if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
            return Integer.compare(a[1], b[1]);
        });
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = mappedNums[i][2];
        }
        return result;
    }
    
    private int getMapped(int num, int[] mapping) {
        if (num == 0) return mapping[0];
        int res = 0;
        int factor = 1;
        List<Integer> digits = new ArrayList<>();
        int temp = num;
        while (temp > 0) {
            digits.add(temp % 10);
            temp /= 10;
        }
        for (int i = digits.size() - 1; i >= 0; i--) {
            res = res * 10 + mapping[digits.get(i)];
        }
        return res;
    }
}
      

var sortJumbled = function(mapping, nums) {
    function mappedValue(num) {
        return parseInt(num.toString().split('').map(d => mapping[parseInt(d)]).join(''));
    }
    // Pair each number with its mapped value and original index for stability
    let mappedNums = nums.map((num, idx) => [mappedValue(num), idx, num]);
    mappedNums.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    return mappedNums.map(pair => pair[2]);
};