LeetCode 2191 - Sort the Jumbled Numbers
The problem asks us to sort an array of integers based on a custom digit mapping rather than their natural numeric value.
Difficulty: 🟡 Medium
Topics: Array, Sorting
Solution
Problem Understanding
The problem asks us to sort an array of integers based on a custom digit mapping rather than their natural numeric value. Each digit from 0 to 9 has a mapped value given in the mapping array, and every number in nums can be "transformed" by replacing each digit according to this mapping. The key point is that the sorting must use these transformed values for comparison, but the original numbers themselves remain in the result. Additionally, if two numbers map to the same transformed value, their relative order in the input must be preserved, which makes this a stable sort problem.
For example, if mapping[3] = 0, any 3 in a number becomes 0 in the mapped value. If two numbers map to the same value, their original order in nums is retained.
Constraints tell us that the array mapping always has 10 unique digits, and nums can have up to 30,000 elements, each up to just under a billion. This means the algorithm needs to be efficient but doesn't need extreme optimizations for very large numbers because Python and Go handle large integers naturally.
Important edge cases include numbers that map to leading zeros after transformation, numbers that are identical after mapping, and very large numbers close to 10^9.
Approaches
The brute-force approach is straightforward: for each number, compute its mapped value, then sort the numbers based on these mapped values using a standard sort function. While correct, this approach could be slightly inefficient because it requires recomputing mapped values multiple times if not cached, and handling large numbers might introduce minor overhead due to string conversions.
The optimal approach leverages stable sorting with precomputed mapped values. By converting each number to its mapped value once and storing a tuple of (mapped_value, original_number), we can sort the array based on mapped values and retrieve the original numbers in sorted order. This ensures stability without extra handling and avoids repeated mapping calculations.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n log n * d) | O(n) | Compute mapped values on the fly during comparison, potentially multiple times per number, where d is the number of digits in the largest number |
| Optimal | O(n log n * d) | O(n) | Precompute mapped values for all numbers, sort by them using stable sort, then extract original numbers |
Algorithm Walkthrough
- Precompute mapped values: For each number in
nums, convert it to a string and replace each digitiwithmapping[i]. Convert the mapped string back to an integer. This ensures numbers with leading zeros are correctly handled. - Pair mapped values with original numbers: Create a list of tuples
(mapped_value, original_number)for every number innums. This allows us to sort based on mapped values while keeping the original numbers intact. - Stable sort: Sort the list of tuples by
mapped_value. Use a stable sorting algorithm to preserve the relative order of numbers with equal mapped values. - Extract sorted original numbers: After sorting, extract the second element from each tuple to obtain the final result.
Why it works: Each number is transformed exactly once, and sorting is based solely on the transformed values. Stability ensures the relative order of numbers with identical mapped values is preserved, satisfying all problem constraints.
Python Solution
from typing import List
class Solution:
def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
def get_mapped_value(num: int) -> int:
mapped_digits = ''.join(str(mapping[int(digit)]) for digit in str(num))
return int(mapped_digits)
# Pair each number with its mapped value
mapped_pairs = [(get_mapped_value(num), num) for num in nums]
# Stable sort based on mapped value
mapped_pairs.sort(key=lambda x: x[0])
# Extract the original numbers in the new order
return [num for _, num in mapped_pairs]
The function get_mapped_value converts each integer into its mapped value by iterating over its digits. We then form tuples pairing mapped values with original numbers. Sorting these tuples using sort with a key ensures a stable sort. Finally, we extract only the original numbers for the result.
Go Solution
import (
"sort"
"strconv"
)
func sortJumbled(mapping []int, nums []int) []int {
type pair struct {
mapped int
original int
}
getMappedValue := func(num int) int {
numStr := strconv.Itoa(num)
mappedStr := ""
for _, c := range numStr {
digit := int(c - '0')
mappedStr += strconv.Itoa(mapping[digit])
}
mappedVal, _ := strconv.Atoi(mappedStr)
return mappedVal
}
pairs := make([]pair, len(nums))
for i, num := range nums {
pairs[i] = pair{getMappedValue(num), num}
}
sort.SliceStable(pairs, func(i, j int) bool {
return pairs[i].mapped < pairs[j].mapped
})
result := make([]int, len(nums))
for i, p := range pairs {
result[i] = p.original
}
return result
}
In Go, we use a custom struct pair to store mapped and original values. strconv functions handle string conversion. sort.SliceStable ensures stability. The logic mirrors the Python solution, adapted for Go's type system and string handling.
Worked Examples
Example 1:
Input: mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]
| Original | Mapped | Notes |
|---|---|---|
| 991 | 669 | 9 → 6, 1 → 9 |
| 338 | 007 → 7 | 3 → 0, 8 → 7; leading zeros removed |
| 38 | 07 → 7 | same as above |
After sorting mapped values: 7, 7, 669 → original order preserved among 7s → [338, 38, 991].
Example 2:
Input: mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]
| Original | Mapped | Notes |
|---|---|---|
| 789 | 789 | identity mapping |
| 456 | 456 | identity mapping |
| 123 | 123 | identity mapping |
After sorting: [123,456,789].
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n * d + n log n) | Each number of up to d digits is mapped in O(d), then sorted in O(n log n) |
| Space | O(n) | Store mapped-original pairs for sorting |
The d term is negligible compared to n log n for large arrays, but must be considered for numbers with many digits.
Test Cases
# Provided examples
assert Solution().sortJumbled([8,9,4,0,2,1,3,5,7,6], [991,338,38]) == [338,38,991]
assert Solution().sortJumbled([0,1,2,3,4,5,6,7,8,9], [789,456,123]) == [123,456,789]
# Edge cases
assert Solution().sortJumbled([1,0,2,3,4,5,6,7,8,9], [10,1,0]) == [0,1,10] # leading zero mapping
assert Solution().sortJumbled([9,8,7,6,5,4,3,2,1,0], [0,1,9,99]) == [9,99,1,0] # reverse mapping
assert Solution().sortJumbled([0,1,2,3,4,5,6,7,8,9], [0]) == [0] # single element
| Test | Why |
|---|---|
| [991,338,38] | Tests mapping and stable order preservation |
| [789,456,123] | Identity mapping |
| [10,1,0] | Tests mapped leading zeros |
| [0,1,9,99] | Tests reverse mapping order |
| [0] | Single-element array edge case |
Edge Cases
One important edge case is numbers that map to leading zeros. For example, if 3 maps to 0, the number 38 becomes 07. Converting back to integer removes the leading zero, correctly comparing to other numbers.
Another edge case is numbers with identical mapped values. Stability is crucial here; numbers like 338 and 38 that both map to 7 must maintain their original input order. The algorithm achieves this by using a stable sort.
A third edge case is single-element arrays. The algorithm must correctly handle arrays with one number, returning it unchanged without error. The mapping function still works, but sorting has no effect.
These edge cases are directly handled in the solution through integer conversion (removing leading zeros), stable sorting, and proper tuple/pair representation.