Sort the Jumbled Numbers

medium array sorting stable sort

Problem

A length-10 array mapping describes a shuffled decimal system: digit i is rewritten as mapping[i]. The mapped value of a number is obtained by replacing each of its digits through this rule (leading zeros vanish, e.g. 007 → 7). Return nums sorted in non-decreasing order of mapped value, without replacing the elements themselves. Numbers with equal mapped values keep their original relative order (a stable sort).

Inputmapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]

Output[338,38,991]

991→669, 338→007=7, 38→07=7. 338 and 38 tie at 7, so they keep input order; 991 sorts last.

mapping (10 digits, comma-separated)

nums (comma-separated)

def sortJumbled(mapping, nums):
    def mapped(n):                         # apply the digit mapping
        digits = str(n)                    # work on the decimal string
        out = "".join(str(mapping[int(c)]) for c in digits)
        return int(out)                    # int() drops leading zeros
    keyed = []
    for i, n in enumerate(nums):           # build (mappedValue, index, value)
        keyed.append((mapped(n), i, n))
    keyed.sort()                           # sort by value, then original index
    return [t[2] for t in keyed]           # emit original numbers in order

function sortJumbled(mapping, nums) {
  function mapped(n) {                       // apply the digit mapping
    const digits = String(n);               // work on the decimal string
    let out = "";
    for (const c of digits) out += mapping[+c];
    return parseInt(out, 10);               // parseInt drops leading zeros
  }
  const keyed = nums.map((n, i) => [mapped(n), i, n]);
  keyed.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // value, then index
  return keyed.map(t => t[2]);              // emit original numbers in order
}

int[] sortJumbled(int[] mapping, int[] nums) {
    int n = nums.length;
    Integer[] idx = new Integer[n];
    long[] mapped = new long[n];
    for (int i = 0; i < n; i++) {            // compute each mapped value
        idx[i] = i;
        String d = Integer.toString(nums[i]);
        StringBuilder sb = new StringBuilder();
        for (char c : d.toCharArray()) sb.append(mapping[c - '0']);
        mapped[i] = Long.parseLong(sb.toString()); // drops leading zeros
    }
    Arrays.sort(idx, (a, b) ->              // value, then original index
        mapped[a] != mapped[b] ? Long.compare(mapped[a], mapped[b]) : a - b);
    int[] res = new int[n];
    for (int i = 0; i < n; i++) res[i] = nums[idx[i]];
    return res;
}

vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
    int n = nums.size();
    vector<array<long long, 3>> keyed(n);    // {mappedValue, index, value}
    for (int i = 0; i < n; i++) {            // compute each mapped value
        string d = to_string(nums[i]), out;
        for (char c : d) out += ('0' + mapping[c - '0']);
        keyed[i] = { stoll(out), i, nums[i] }; // stoll drops leading zeros
    }
    sort(keyed.begin(), keyed.end());        // value, then index, then value
    vector<int> res(n);
    for (int i = 0; i < n; i++) res[i] = (int) keyed[i][2];
    return res;
}

Explanation

The trick is to sort by a derived key instead of the numbers themselves. For every number we compute its mapped value once, then sort the numbers by that value while leaving the actual numbers untouched.

Computing a mapped value is a simple per-digit substitution. Turn the number into its decimal string, replace each character c with mapping[c], and parse the result back to an integer. Parsing as an integer naturally throws away any leading zeros — that is why 338 → 007 becomes just 7.

To keep the sort stable (equal mapped values stay in input order) we attach the original index to each entry and break ties by it. So each entry is a triple (mappedValue, index, originalNumber); sorting these triples lexicographically does exactly what we want, and we read off the originalNumber field at the end.

Example: mapping = [8,9,4,0,2,1,3,5,7,6]. Then 991 → 669, 338 → 007 = 7, and 38 → 07 = 7. The keys are (669,0), (7,1), (7,2). Sorted: (7,1) < (7,2) < (669,0), giving [338, 38, 991].

Because each mapped value depends only on its own digits, mapping costs O(d) per number (d = number of digits, at most 10 here), and the sort dominates at O(N log N).

Time: O(N log N) Space: O(N)