{x}
blog image

Sort the Jumbled Numbers

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

Solution Explanation for Sort the Jumbled Numbers

This problem requires sorting an array of integers based on their mapped values, determined by a given mapping array. The mapping array translates each digit (0-9) to a new digit. The solution involves creating a custom sorting function that considers these mapped values.

Approach

The core idea is to use a custom sorting function that calculates the mapped value for each number in the input array (nums). This mapped value is used as the key for sorting. To preserve the original order of numbers with the same mapped value, we also include the original index of the number as a secondary sorting key.

The process involves these steps:

  1. Map Function: A helper function f(x) is defined to calculate the mapped value of an integer x. This function iterates through the digits of x, looks up the mapped digit in the mapping array, and constructs the new mapped integer.

  2. Create Sorting Data: We create a temporary array (e.g., arr in the code examples) of pairs. Each pair contains the mapped value (f(x)) and the original index of the corresponding number in nums.

  3. Sort: This temporary array is sorted using a custom comparison function. The comparison function first compares the mapped values. If the mapped values are equal, it compares the original indices to maintain the relative order of numbers with the same mapped value.

  4. Reconstruct Result: Finally, we iterate through the sorted temporary array and reconstruct the sorted nums array using the original indices stored in the pairs.

Time and Space Complexity Analysis

  • Time Complexity: The dominant operation is sorting the temporary array arr. The size of arr is equal to the length of the input array nums (denoted as n). The sorting algorithm's time complexity is O(n log n) in most cases (e.g., merge sort or quicksort). The mapping function f(x) has a time complexity of O(log x) because the number of digits in x is proportional to log10(x). However, since x is bounded by constraints, the mapping is considered O(1) on average. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

  • Space Complexity: The space complexity is determined by the temporary array arr, which stores n pairs. Therefore, the space complexity is O(n). This is considered linear space complexity.

Code Examples (with explanations in comments)

The code examples provided in the previous response demonstrate this approach in several programming languages. The comments in the code explain the individual steps in detail. The key parts to notice are the f(x) function for mapping, the creation of the pairs array, and the custom sorting function.