Problem Description

You have a special mapping system that changes how digits are interpreted. The mapping array tells you how to transform each digit: if mapping[i] = j, then digit i should be read as digit j.

Given this mapping system and an array of integers nums, you need to:

1. Transform each number in nums using the mapping rules. For example, if mapping = [2,1,3,4,5,6,7,8,9,0] and you have the number 123, you would:

   • Replace digit 1 with mapping[1] = 1
   • Replace digit 2 with mapping[2] = 3
   • Replace digit 3 with mapping[3] = 4
   • Getting mapped value 134

2. Sort the array based on these mapped values in ascending order. The original numbers in nums stay the same - you're just sorting them based on what they map to.

3. Maintain relative order for numbers that have the same mapped value (stable sort).

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

• 991 maps to 669 (9→6, 9→6, 1→9)
• 338 maps to 007 = 7 (3→0, 3→0, 8→7)
• 38 maps to 07 = 7 (3→0, 8→7)

Since 338 and 38 both map to 7, and 338 appears before 38 in the original array, the sorted result would be [338, 38, 991].

The solution creates tuples of (mapped_value, original_index) for each number, sorts these tuples, then reconstructs the final array using the sorted indices.

Intuition

The key insight is that we need to sort numbers based on their "translated" values while keeping the original numbers intact. This is like sorting people by their nicknames while still remembering their real names.

Since we can't directly modify the numbers in nums, we need a way to:

1. Calculate what each number "looks like" after mapping
2. Sort based on these mapped values
3. Return the original numbers in the new order

The challenge is converting each digit in a number according to the mapping. For a number like 338, we need to extract each digit (3, 3, 8), map them individually (0, 0, 7), and reconstruct the mapped number (007 = 7).

To extract digits, we can repeatedly use divmod(x, 10) which gives us the last digit and the remaining number. As we process each digit from right to left, we multiply by increasing powers of 10 to rebuild the mapped number in the correct position.

For maintaining stable sort (elements with same mapped values keep their relative order), we pair each mapped value with its original index: (mapped_value, index). When Python sorts tuples, it first sorts by the first element, then by the second element for ties. Since indices naturally increase, this preserves the original order for equal mapped values.

The special case of x == 0 needs separate handling because the while loop wouldn't execute for zero (since while 0 is false), but we still need to map the single digit 0 to mapping[0].

Learn more about Sorting patterns.

Solution Approach

The solution uses custom sorting with a helper function to calculate mapped values.

Step 1: Create the mapping function f(x)

The function takes an integer and returns its mapped value:

• Handle the special case where x == 0: directly return mapping[0]
• For other numbers, extract digits one by one using divmod(x, 10):
  • x, v = divmod(x, 10) gives us the last digit v and remaining number x
  • Map the digit: v = mapping[v]
  • Reconstruct the mapped number by building it from right to left: y = k * v + y
  • k tracks the current position value (1, 10, 100, ...) and multiplies by 10 each iteration

Step 2: Create sortable tuples

For each element in nums, create a tuple (f(x), i) where:

• f(x) is the mapped value of nums[i]
• i is the original index

This is done using a generator expression: (f(x), i) for i, x in enumerate(nums)

Step 3: Sort the tuples

sorted() sorts the tuples first by mapped value, then by index. Since indices are already in ascending order, this naturally maintains stability - elements with the same mapped value keep their relative order.

Step 4: Extract the result

From the sorted array of tuples arr, extract the indices and use them to build the final result: [nums[i] for _, i in arr]

The time complexity is O(n log n) for sorting, where n is the length of nums. The space complexity is O(n) for storing the array of tuples.

Example Walkthrough

Let's walk through a small example with mapping = [3,1,2,5,4,0,6,7,8,9] and nums = [24, 15, 5].

Step 1: Calculate mapped values using function f(x)

For 24:

• Extract digits: 24 → 2, 4
• Starting with rightmost digit 4: mapping[4] = 4
• Next digit 2: mapping[2] = 2
• Reconstruct: 2 * 10 + 4 = 24 (maps to itself!)

For 15:

• Extract digits: 15 → 1, 5
• Starting with rightmost digit 5: mapping[5] = 0
• Next digit 1: mapping[1] = 1
• Reconstruct: 1 * 10 + 0 = 10

For 5:

• Single digit: mapping[5] = 0
• Result: 0

Step 2: Create (mapped_value, index) tuples

• 24 at index 0 → (24, 0)
• 15 at index 1 → (10, 1)
• 5 at index 2 → (0, 2)

Tuples array: [(24, 0), (10, 1), (0, 2)]

Step 3: Sort the tuples by mapped value

Sorting by first element (mapped value):

• (0, 2) - smallest mapped value
• (10, 1) - middle mapped value
• (24, 0) - largest mapped value

Sorted array: [(0, 2), (10, 1), (24, 0)]

Step 4: Extract original numbers using sorted indices

From sorted tuples, take indices: 2, 1, 0

• Index 2 → nums[2] = 5
• Index 1 → nums[1] = 15
• Index 0 → nums[0] = 24

Final result: [5, 15, 24]

The original array [24, 15, 5] has been sorted to [5, 15, 24] based on their mapped values (24→24, 15→10, 5→0).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × m × log n) where n is the length of the array nums and m is the average number of digits in the numbers.

The time complexity breaks down as follows:

• The function f(x) processes each digit of a number, taking O(m) time where m is the number of digits
• We call f(x) for each of the n numbers in nums, resulting in O(n × m) time
• The sorting operation on n elements takes O(n × log n) time
• Total complexity: O(n × m) + O(n × log n) = O(n × m × log n)

However, if we consider m (the maximum number of digits) as a constant since integers have a bounded number of digits in practice, the time complexity simplifies to O(n × log n).

Space Complexity: O(n)

The space complexity analysis:

• The arr list stores tuples (f(x), i) for each element, requiring O(n) space
• The final list comprehension creates a new list of size n, requiring O(n) space
• The function f(x) uses O(1) auxiliary space for variables y, k, and v
• Total space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Handling Zero

A common mistake is forgetting that 0 is a special case. When processing digits with divmod, the loop while number > 0 will never execute for number = 0, resulting in returning 0 instead of mapping[0].

Incorrect approach:

def get_mapped_value(number: int) -> int:
    mapped_result = 0
    position_multiplier = 1
  
    while number > 0:  # This loop never runs when number = 0!
        number, digit = divmod(number, 10)
        mapped_digit = mapping[digit]
        mapped_result = position_multiplier * mapped_digit + mapped_result
        position_multiplier *= 10
  
    return mapped_result  # Returns 0 instead of mapping[0]

Solution: Always check for zero as a special case before the loop.

2. Digit Reconstruction Order Error

Another pitfall is building the mapped number in the wrong order. Since we extract digits from right to left, we must carefully reconstruct the mapped value to maintain the correct digit positions.

Incorrect approach:

# Wrong: Simply appending digits leads to reversed number
mapped_result = mapped_result * 10 + mapped_digit  # This reverses the digits!

Solution: Use mapped_result = position_multiplier * mapped_digit + mapped_result to maintain correct digit positions.

3. Using Unstable Sorting

If you don't maintain the original indices when creating the sortable data structure, you might lose the relative order of elements with the same mapped value.

Incorrect approach:

# Wrong: Only sorting by mapped values loses stability
mapped_values = [get_mapped_value(num) for num in nums]
# How do we know which original number each mapped value came from?

Solution: Create tuples with both mapped values and original indices: (mapped_value, index). Python's sort is stable and will preserve the original order for equal mapped values.

4. String Conversion Inefficiency

Some might be tempted to convert numbers to strings for digit manipulation, which is less efficient and can introduce edge cases.

Less optimal approach:

def get_mapped_value(number: int) -> int:
    num_str = str(number)
    mapped_str = ''.join(str(mapping[int(digit)]) for digit in num_str)
    return int(mapped_str)  # Potential issues with leading zeros

This approach has problems:

• Less efficient due to string operations
• May incorrectly handle cases where mapped digits create leading zeros (e.g., if mapping[3] = 0, then 38 might become "08" which converts to 8 instead of maintaining the structure)

Solution: Stick with mathematical operations using divmod for better performance and correctness.