# Sort the Jumbled Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sort-the-jumbled-numbers)
Canonical: https://scaleengineer.com/dsa/problems/sort-the-jumbled-numbers
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** integer array `mapping` which represents the mapping rule of a shuffled decimal system. `mapping[i] = j` means digit `i` should be mapped to digit `j` in this system.

The **mapped value** of an integer is the new integer obtained by replacing each occurrence of digit `i` in the integer with `mapping[i]` for all `0 <= i <= 9`.

You are also given another integer array `nums`. Return _the array_ `nums` _sorted in **non-decreasing** order based on the **mapped values** of its elements._

**Notes:**

* Elements with the same mapped values should appear in the **same relative order** as in the input.
* The elements of `nums` should only be sorted based on their mapped values and **not be replaced** by them.

**Example 1:**

**Input:** mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]
**Output:** [338,38,991]
**Explanation:** 
Map the number 991 as follows:
1. mapping[9] = 6, so all occurrences of the digit 9 will become 6.
2. mapping[1] = 9, so all occurrences of the digit 1 will become 9.
Therefore, the mapped value of 991 is 669.
338 maps to 007, or 7 after removing the leading zeros.
38 maps to 07, which is also 7 after removing leading zeros.
Since 338 and 38 share the same mapped value, they should remain in the same relative order, so 338 comes before 38.
Thus, the sorted array is [338,38,991].

**Example 2:**

**Input:** mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]
**Output:** [123,456,789]
**Explanation:** 789 maps to 789, 456 maps to 456, and 123 maps to 123. Thus, the sorted array is [123,456,789].

**Constraints:**

* `mapping.length == 10`
* `0 <= mapping[i] <= 9`
* All the values of `mapping[i]` are **unique**.
* `1 <= nums.length <= 3 * 104`
* `0 <= nums[i] < 109`

# Approaches
## Custom Sort with On-the-fly Calculation
This approach involves using a standard sorting algorithm with a custom comparator. The comparator calculates the mapped value for two numbers on the fly during each comparison. Because comparison-based sorting algorithms like Timsort (used by `Collections.sort`) compare elements multiple times, the mapped value for a single number will be computed repeatedly, leading to poor performance.
**Time:** O(N * log(N) * D), where `N` is the number of elements in `nums` and `D` is the maximum number of digits in a number from `nums`. The sort takes `O(N * log(N))` comparisons. Each comparison involves two calls to `getMappedValue`, which takes `O(D)` time. · **Space:** O(N + D). `O(N)` is required to store the list of numbers. `O(D)` is used for the string builder within the `getMappedValue` function. The sort itself (Timsort) can take up to `O(N)` space in the worst case.
**Pros:** Relatively simple to understand and implement using standard library functions.; Code is concise.
**Cons:** Inefficient due to redundant computations of mapped values. The mapped value for a single number is recalculated every time it's involved in a comparison during the sort.
### Explanation
The core of this method is a custom comparison logic that we provide to a sorting function. First, we need a helper function, let's call it `getMappedValue`, which takes an integer, converts it to a string, replaces each digit character according to the `mapping` array, and then parses the resulting string back to an integer. For example, if `num = 991` and `mapping[9]=6`, `mapping[1]=9`, `getMappedValue(991)` would convert `991` to `"991"`, map it to `"669"`, and return the integer `669`.

Since standard sorts on primitive arrays (like `int[]`) in Java are not guaranteed to be stable, we first convert the `nums` array into a `List<Integer>`. We then use `Collections.sort()` on this list, providing a lambda expression as the comparator. This comparator `(a, b) -> ...` will call `getMappedValue(a)` and `getMappedValue(b)` and compare the results. `Collections.sort()` is a stable sort, which satisfies the problem's requirement for elements with equal mapped values.

Finally, the sorted list is converted back into an `int[]` array. The main drawback is the performance hit from re-calculating mapped values. A number might be part of `O(log N)` comparisons, leading to `O(log N)` calculations of its mapped value.

```java
class Solution {
    public int[] sortJumbled(int[] mapping, int[] nums) {
        List<Integer> numsList = new ArrayList<>();
        for (int num : nums) {
            numsList.add(num);
        }

        // Sort using a custom comparator that calculates mapped values on the fly
        Collections.sort(numsList, (a, b) -> {
            long mappedA = getMappedValue(a, mapping);
            long mappedB = getMappedValue(b, mapping);
            return Long.compare(mappedA, mappedB);
        });

        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = numsList.get(i);
        }
        return result;
    }

    private long getMappedValue(int n, int[] mapping) {
        char[] s = Integer.toString(n).toCharArray();
        for (int i = 0; i < s.length; i++) {
            s[i] = (char) (mapping[s[i] - '0'] + '0');
        }
        return Long.parseLong(new String(s));
    }
}
```
### Algorithm
- Convert the input `int[] nums` to a `List<Integer>` to leverage Java's stable `Collections.sort`.
- Define a helper function `getMappedValue(num, mapping)` that:
  - Converts `num` to its string representation.
  - Iterates through each character (digit) of the string.
  - Replaces the digit with its mapped value from the `mapping` array.
  - Builds a new string with the mapped digits.
  - Parses the new string back to a number. It's safer to parse to a `long` to avoid potential overflow, though an `int` might suffice given the constraints.
- Sort the list using `Collections.sort` with a custom comparator.
- The comparator takes two numbers, `a` and `b`, calls `getMappedValue` for both, and compares the results.
- Copy the elements from the sorted list back to an `int[]` array.
- Return the result array.

## Pre-computation and Comparison Sort
This approach improves upon the first one by avoiding redundant calculations. We first compute the mapped value for every number in `nums` just once and store it. Then, we sort the original numbers based on these pre-computed mapped values using a standard comparison-based sort.
**Time:** O(N * log(N) + N * D). `N` is the number of elements in `nums`, and `D` is the max number of digits. The first term is for sorting, and the second is for computing all mapped values. Since `D` is a small constant (<= 10), the complexity is effectively `O(N * log(N))`. · **Space:** O(N). We need `O(N)` space for the `pairedNums` array. The sorting algorithm might also use `O(log N)` or `O(N)` auxiliary space.
**Pros:** Much more efficient than the first approach as it avoids recomputing mapped values.; Still relatively easy to implement using built-in sort functions.
**Cons:** Requires extra space (`O(N)`) to store the pairs of mapped and original values.; Not as asymptotically fast as a linear-time sorting algorithm like Radix Sort.
### Explanation
The key idea is to decouple the calculation of mapped values from the sorting comparison logic. We create a data structure to hold pairs of information: the original number and its corresponding mapped value. A 2D array `int[][] pairedNums` of size `N x 2` is a good choice, where `N` is the length of `nums`.

We iterate through the `nums` array once. For each number `nums[i]`, we calculate its mapped value and store the pair `{mappedValue, originalNumber}` in our `pairedNums` array. For example, `pairedNums[i] = {getMappedValue(nums[i]), nums[i]}`.

After populating the `pairedNums` array, we sort it based on the first element of each pair (the mapped value). `Arrays.sort` with a custom comparator `(a, b) -> Integer.compare(a[0], b[0])` works perfectly. Since `Arrays.sort` for objects (and 2D arrays are arrays of objects) is stable in Java, if two numbers have the same mapped value, their original relative order is preserved because we populated `pairedNums` in the original order.

Finally, we create the result array by extracting the second element (the original number) from each pair in the now-sorted `pairedNums` array.

```java
class Solution {
    public int[] sortJumbled(int[] mapping, int[] nums) {
        int n = nums.length;
        int[][] pairedNums = new int[n][2];

        for (int i = 0; i < n; i++) {
            int originalNum = nums[i];
            int mappedNum = getMappedValue(originalNum, mapping);
            pairedNums[i][0] = mappedNum;
            pairedNums[i][1] = originalNum;
        }

        // Sort the pairs based on the mapped value
        Arrays.sort(pairedNums, (a, b) -> Integer.compare(a[0], b[0]));

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = pairedNums[i][1];
        }
        return result;
    }

    private int getMappedValue(int n, int[] mapping) {
        char[] s = Integer.toString(n).toCharArray();
        for (int i = 0; i < s.length; i++) {
            s[i] = (char) (mapping[s[i] - '0'] + '0');
        }
        return Integer.parseInt(new String(s));
    }
}
```
### Algorithm
- Create a 2D array `pairedNums` of size `N x 2` to store `[mapped_value, original_number]`.
- Iterate through the input `nums` array from `i = 0` to `N-1`.
- For each `nums[i]`, calculate its mapped value using a helper function.
- Store the mapped value and the original number as a pair: `pairedNums[i] = {mappedValue, nums[i]}`.
- Sort the `pairedNums` array based on the first column (the mapped values) using a stable comparison sort like `Arrays.sort` with a lambda comparator.
- Initialize a new result array.
- Iterate through the sorted `pairedNums` array and populate the result array with the second column (the original numbers).
- Return the result array.

## Linear Time Sort using Radix Sort
This is the most optimal approach in terms of time complexity. After computing the mapped values and pairing them with their original numbers, we use Radix Sort instead of a comparison-based sort. Radix Sort is a non-comparison integer sorting algorithm that can sort numbers in linear time. Since Radix Sort is inherently stable, it naturally handles the requirement to preserve the relative order for elements with the same mapped value.
**Time:** O(N * D + D_max * (N + B)). `N` is the number of elements, `D` is the average number of digits in `nums`, `D_max` is the number of digits in the maximum mapped value (a constant, at most 10), and `B` is the base (10). Since `D`, `D_max`, and `B` are small constants, the overall complexity simplifies to `O(N)`. · **Space:** O(N + B). `O(N)` is needed to store the pairs. The Counting Sort subroutine requires `O(N + B)` space for the output array and the count array, where `B` is the base (10). This simplifies to `O(N)`.
**Pros:** Asymptotically the fastest approach with linear time complexity.; Highly efficient for large inputs.
**Cons:** More complex to implement correctly compared to using a built-in sorting function.; The constant factors might make it slower than a highly optimized library `sort` for smaller input sizes, despite better asymptotic complexity.
### Explanation
This approach also starts by pre-computing mapped values, similar to the second approach. We create pairs of `(mapped_value, original_number)`. The key difference is the sorting algorithm used.

Instead of `Arrays.sort`, which has a time complexity of `O(N log N)`, we implement Radix Sort. Radix sort works by sorting numbers digit by digit, from the least significant digit to the most significant. To ensure the overall sort is correct, the sorting algorithm used for each digit must be stable. Counting Sort is a perfect candidate for this stable, linear-time subroutine.

We find the maximum mapped value to determine how many digits (passes) we need. For each digit place (1s, 10s, 100s, etc.), we perform a Counting Sort on our array of pairs. The "key" for the counting sort is the digit at the current place for the `mapped_value` of each pair.

After all passes are complete, the array of pairs will be sorted according to the `mapped_value`. We then extract the `original_number` from each pair to construct the final result.

```java
class Solution {
    public int[] sortJumbled(int[] mapping, int[] nums) {
        int n = nums.length;
        int[][] pairs = new int[n][2]; // [mapped_value, original_number]
        for (int i = 0; i < n; i++) {
            pairs[i][0] = getMappedValue(nums[i], mapping);
            pairs[i][1] = nums[i];
        }

        radixSort(pairs);

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = pairs[i][1];
        }
        return result;
    }

    private int getMappedValue(int n, int[] mapping) {
        char[] s = Integer.toString(n).toCharArray();
        for (int i = 0; i < s.length; i++) {
            s[i] = (char) (mapping[s[i] - '0'] + '0');
        }
        return Integer.parseInt(new String(s));
    }

    private void radixSort(int[][] pairs) {
        int maxVal = 0;
        for (int[] pair : pairs) {
            maxVal = Math.max(maxVal, pair[0]);
        }

        long exp = 1;
        while (maxVal / exp > 0) {
            countingSort(pairs, exp);
            exp *= 10;
        }
    }

    private void countingSort(int[][] pairs, long exp) {
        int n = pairs.length;
        int[][] output = new int[n][2];
        int[] count = new int[10]; // For digits 0-9

        for (int i = 0; i < n; i++) {
            int digit = (int) ((pairs[i][0] / exp) % 10);
            count[digit]++;
        }

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; i--) {
            int digit = (int) ((pairs[i][0] / exp) % 10);
            int index = count[digit] - 1;
            output[index][0] = pairs[i][0];
            output[index][1] = pairs[i][1];
            count[digit]--;
        }

        System.arraycopy(output, 0, pairs, 0, n);
    }
}
```
### Algorithm
- Create a data structure (e.g., a 2D array or a list of custom objects) to store pairs of `(mapped_value, original_number)`.
- Iterate through `nums`, calculate the mapped value for each number, and populate the list of pairs.
- Implement Radix Sort to sort this list of pairs based on the `mapped_value`.
  - Find the maximum mapped value to determine the number of passes.
  - Loop from the least significant digit to the most significant digit (`exp = 1, 10, 100, ...`).
  - In each loop, use a stable sorting algorithm like Counting Sort to sort the pairs based on the current digit of their `mapped_value`.
- After the Radix Sort is complete, the list of pairs is sorted.
- Create a result array and populate it with the `original_number` from the sorted pairs.
- Return the result array.

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] SortJumbled(int[] mapping, int[] nums) {
        Func < int, int > f = (int x) => {
            if (x == 0) {
                return mapping[0];
            }
            int y = 0;
            int k = 1;
            int num = x;
            while (num != 0) {
                int v = mapping[num % 10];
                y = k * v + y;
                k *= 10;
                num /= 10;
            }
            return y;
        };
        int n = nums.Length;
        List < (int, int) > arr = new List < (int, int) > ();
        for (int i = 0; i < n; ++i) {
            arr.Add((f(nums[i]), i));
        }
        arr.Sort();
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = nums[arr[i].Item2];
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int[] sortJumbled(int[] mapping, int[] nums) {
    int n = nums.length;
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; ++i) {
      int x = nums[i];
      int y = x == 0 ? mapping[0] : 0;
      int k = 1;
      for (; x > 0; x /= 10) {
        y += k * mapping[x % 10];
        k *= 10;
      }
      arr[i] = new int[]{y, i};
    }
    Arrays.sort(arr, (a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      ans[i] = nums[arr[i][1]];
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} mapping * @param {number[]} nums * @return {number[]} */ var sortJumbled =
  function (mapping, nums) {
    const n = nums.length;
    const f = (x) => {
      if (x === 0) {
        return mapping[0];
      }
      let y = 0;
      for (let k = 1; x; x = (x / 10) | 0) {
        const v = mapping[x % 10];
        y += v * k;
        k *= 10;
      }
      return y;
    };
    const arr = nums.map((x, i) => [f(x), i]);
    arr.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));
    return arr.map((x) => nums[x[1]]);
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> sortJumbled(vector<int> &mapping, vector<int> &nums) {
    int n = nums.size();
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; ++i) {
      int x = nums[i];
      int y = x == 0 ? mapping[0] : 0;
      int k = 1;
      for (; x; x /= 10) {
        y += k * mapping[x % 10];
        k *= 10;
      }
      arr[i] = {y, i};
    }
    sort(arr.begin(), arr.end());
    vector<int> ans;
    for (auto &[_, i] : arr) {
      ans.push_back(nums[i]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]: arr = [] for i, x in enumerate(nums): y = mapping[0] if x == 0 else 0 k = 1 while x: x, v = divmod(x, 10) y = mapping[v] * k + y k *= 10 arr . append((y, i)) arr . sort() return [nums[i] for _, i in arr]

```