#2191

Medium

LeetCode Problem Workspace

Sort the Jumbled Numbers

Sort numbers based on a custom mapping of their digits, leveraging array manipulation and sorting techniques.

Problem Statement

You are given an integer array mapping of length 10, where each element represents the new value of a digit in a custom decimal system. mapping[i] means the digit i is replaced by mapping[i].

Additionally, you are given an array of integers nums. Your task is to sort nums in non-decreasing order based on the mapped values of each number. The mapped value of a number is the result of replacing each of its digits with the corresponding value from the mapping array.

Examples

Example 1

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

Output: [338,38,991]

Map the number 991 as follows:

mapping[9] = 6, so all occurrences of the digit 9 will become 6.
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]

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 Approach

Mapping Transformation

For each number in nums, convert the number to its mapped form by replacing each digit with its corresponding mapped value from the mapping array. This transformation ensures that the original numbers are accurately represented in the new system.

Sorting Based on Mapped Values

Once each number has been transformed into its mapped form, sort the numbers based on their mapped values. If two numbers have the same mapped value, maintain their relative order as given in the original array to preserve stability.

Efficient Sorting Algorithm

The problem can be solved in O(n log n) time by leveraging sorting algorithms. The key part is the mapped transformation which ensures the sorting is based on a modified comparison, efficiently handled by standard sorting algorithms like MergeSort or QuickSort.

Complexity Analysis

Metric	Value
Time	O(n\cdot \log n)
Space	O(n)

The time complexity is O(n log n) due to the sorting operation, where n is the length of the nums array. The space complexity is O(n) to store the transformed mapped values of the numbers in a new array before sorting.

What Interviewers Usually Probe

Look for candidates who understand how mapping and sorting can be combined for a custom sorting problem.
Candidates should demonstrate understanding of stability in sorting, ensuring that equal mapped values preserve their relative order.
Expect candidates to efficiently handle mapping transformations and sorting of numbers in non-decreasing order.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the mapping transformation and mistakenly modifying the original numbers without mapping their digits first.
Not maintaining the relative order of numbers when their mapped values are the same, causing incorrect sorting results.
Inefficient mapping and sorting logic, leading to higher time complexity than the expected O(n log n).

Follow-up variants

Increasing the length of the nums array to test performance under larger inputs.
Adjusting the mapping to include digits in reverse order or with repeated values, affecting the mapping logic.
Providing edge cases where nums contains a single element or multiple elements with identical mapped values.

FAQ

What is the key pattern in the Sort the Jumbled Numbers problem?

The problem revolves around transforming numbers using a custom mapping and sorting them based on these mapped values, combining array manipulation and sorting techniques.

How does mapping affect the sorting order in this problem?

The sorting order is determined by the transformed (mapped) values of the numbers. The key is to ensure that numbers with the same mapped value maintain their relative order from the original array.

What are the time and space complexities of solving this problem?

The time complexity is O(n log n) due to the sorting operation, and the space complexity is O(n) for storing the mapped values before sorting.

Can this problem be solved without sorting?

Sorting is essential in this problem because the goal is to return the numbers in non-decreasing order based on their mapped values, so sorting is the most direct approach.

What are some common mistakes when solving the Sort the Jumbled Numbers problem?

Common mistakes include failing to correctly map the digits, not maintaining the stability of sorting for equal mapped values, and using inefficient algorithms for large inputs.

terminal

Solution

Solution 1: Custom Sorting

We traverse each element $nums[i]$ in the array $nums$, store its mapped value $y$ and index $i$ into the array $arr$, then sort the array $arr$. Finally, we extract the index $i$ from the sorted array $arr$, convert it to the element $nums[i]$ in the original array $nums$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        def f(x: int) -> int:
            if x == 0:
                return mapping[0]
            y, k = 0, 1
            while x:
                x, v = divmod(x, 10)
                v = mapping[v]
                y = k * v + y
                k *= 10
            return y

        arr = sorted((f(x), i) for i, x in enumerate(nums))
        return [nums[i] for _, i in arr]

Continue Practicing

#2195 append k integers with minimal sum #2171 removing minimum number of magic beans #2164 sort even and odd indices independently