Watch 10 video solutions for Sort the Jumbled Numbers, a medium level problem involving Array, Sorting. This walkthrough by NeetCodeIO has 8,688 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 == 100 <= mapping[i] <= 9mapping[i] are unique.1 <= nums.length <= 3 * 1040 <= nums[i] < 109Problem Overview: You receive a digit mapping from 0–9 and a list of numbers. Each digit in a number must be replaced using this mapping to produce a transformed value. The array must then be sorted based on these mapped values while preserving the relative order of elements with equal mapped results.
Approach 1: Mapping and Sorting Using Tuples (O(n log n))
Convert every number into its mapped value by replacing each digit using the provided mapping array. For example, if digit 3 maps to 8, every occurrence of 3 in the number becomes 8. Iterate through each number, construct its mapped integer, and store a tuple like (mappedValue, originalIndex, originalNumber). Sorting these tuples ensures numbers are ordered by their mapped value while the original index keeps the order stable when mapped values are equal. Sorting takes O(n log n) time, and building mapped values costs O(d) per number (where d is digit count). Extra space usage is O(n) for the tuple list. This approach is straightforward and commonly used in array + sorting problems.
Approach 2: In-place Reordering Using Custom Comparator (O(n log n))
Instead of storing tuples, compute mapped values during comparisons using a custom comparator. For each comparison, convert both numbers into their mapped forms and compare those integers. Languages like C++ and Java allow custom comparators directly inside sort. The transformation logic extracts digits, replaces them using the mapping, and reconstructs the mapped number. This keeps auxiliary storage minimal since you sort the original array directly. Time complexity remains O(n log n) comparisons with O(d) digit processing per comparison, and space complexity is O(1) apart from the sorting stack. This pattern is common when implementing custom ordering logic in sorting problems.
Recommended for interviews: The tuple-based mapping approach is the safest explanation during interviews. It separates transformation and sorting, making the logic easy to reason about and avoiding repeated digit conversions during comparisons. Showing the comparator version afterward demonstrates deeper understanding of sorting mechanics and space optimization in array processing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Mapping and Sorting Using Tuples | O(n log n) | O(n) | General case. Easiest to implement and guarantees stable ordering using stored indices. |
| In-place Reordering Using Custom Comparator | O(n log n) | O(1) | When minimizing extra memory and the language supports efficient custom comparators. |