Sort the Jumbled Numbers solution and explanation
9 more videos on this problem
Sort the Jumbled Numbers - Leetcode 2191 - PythonNeetCodeIO · 12:37 · 8K views
Sort the Jumbled Numbers | 2 Approaches | Leetcode 2191 | codestorywithMIKcodestorywithMIK · 27:05 · 8K views
2191. Sort the Jumbled Numbers || Biweekly Contest 73 || Leetcode 2191Bro Coders · 7:26 · 3K views
2191. Sort the Jumbled Numbers (Leetcode Medium)Programming Live with Larry · 3:25 · 849 views
Sort the jumbled numbers | Leetcode - 2191 | Bi-weekly contest 73 | SolutionThe Growth Stack · 10:01 · 483 views
Daily Leetcode #1576: Jul 24, 2024 - 2191. Sort the Jumbled NumbersProgramming Live with Larry · 4:14 · 297 views
Leetcode 2191. Sort the Jumbled Numbers (sorting)LetsCode · 6:29 · 246 views
LeetCode 2191 - Sort the Jumbled Numbers - JavaAlpha-Code · 9:40 · 154 views
Sort the Jumbled Numbers (LeetCode 2191) (2 Ways)CodeWithARB · 14:41 · 150 views
2191. Sort the Jumbled Numbers (LeetCode, Java)hakunamatasq · 15:22 · 119 views
The problem
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
numsshould 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] <= 9- All the values of
mapping[i]are unique. 1 <= nums.length <= 3 * 1040 <= nums[i] < 109
Approach overview
Problem 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 1: Approach 1: Mapping and Sorting Using Tuples
Explanation: To sort the numbers in 'nums' according to their mapped values, we'll first calculate the mapped value for each number. We can achieve this by creating a helper function that translates each digit using the given 'mapping' array. Then, we can pair each original number with its mapped value as tuples and sort these tuples based on the mapped values. This ensures that the relative order is maintained for numbers with the same mapped value.
def sortJumbled(mapping, nums):
def mapped_value(num):
return int(''.join(str(mapping[int(digit)]) for digit in str(num)))
return [num for num, _ in sorted((num, mapped_value(num)) for num in nums, key=lambda x: x[1])]
# Example usage:
mapping = [8,9,4,0,2,1,3,5,7,6]
nums = [991,338,38]
print(sortJumbled(mapping, nums)) # Output: [338, 38, 991]function sortJumbled(mapping, nums) {
const mappedValue = (num) => {
return parseInt(num.toString().split('').map(digit => mapping[digit]).join(''), 10);
};
return nums.map(num => [num, mappedValue(num)])
.sort((a, b) => a[1] - b[1])
.map(pair => pair[0]);
}
// Example usage:
const mapping = [0,1,2,3,4,5,6,7,8,9];
const nums = [789,456,123];
console.log(sortJumbled(mapping, nums)); // Output: [123, 456, 789]The code defines a function mapped_value that converts a given number into its mapped equivalent using the 'mapping' array. We iterate through each number in 'nums', pair it with its mapped value, and sort these pairs based on the mapped values (using a lambda function as the key for sorting). Finally, we extract and return just the numbers in their new order.
Time Complexity: O(n * k log k), where n is the number of elements in 'nums' and k is the average number of digits in the numbers. This complexity arises from mapping each digit (O(k)) and sorting (O(n log n)).
Space Complexity: O(n) for storing the tuples of numbers and their mapped values.
Approach 2: Approach 2: In-place Reordering Using Custom Comparator
Explanation: Instead of creating tuples, we can use a custom comparator function directly in our sort operation. This comparator will determine the order based on mapped values of numbers. By transforming the comparator function, we ensure in-place sorting, minimizing additional memory usage.
import java.util.Arrays;
public class SortJumbled {
public static void sortJumbled(int[] mapping, int[] nums) {
Arrays.sort(nums, (a, b) -> {
int mappedA = mappedValue(a, mapping);
int mappedB = mappedValue(b, mapping);
return Integer.compare(mappedA, mappedB);
});
}
private static int mappedValue(int num, int[] mapping) {
StringBuilder mappedStr = new StringBuilder();
for (char c : String.valueOf(num).toCharArray()) {
mappedStr.append(mapping[c - '0']);
}
return Integer.parseInt(mappedStr.toString());
}
public static void main(String[] args) {
int[] mapping = {0,1,2,3,4,5,6,7,8,9};
int[] nums = {789,456,123};
sortJumbled(mapping, nums);
System.out.println(Arrays.toString(nums)); // Output: [123, 456, 789]
}
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int mappedValue(int num, const std::vector<int>& mapping) {
std::string str = std::to_string(num);
for (char& c : str) {
c = '0' + mapping[c - '0'];
}
return std::stoi(str);
}
std::vector<int> sortJumbled(const std::vector<int>& mapping, std::vector<int>& nums) {
std::sort(nums.begin(), nums.end(), [&mapping](int a, int b) {
return mappedValue(a, mapping) < mappedValue(b, mapping);
});
return nums;
}
int main() {
std::vector<int> mapping = {8,9,4,0,2,1,3,5,7,6};
std::vector<int> nums = {991,338,38};
std::vector<int> result = sortJumbled(mapping, nums);
for (int num : result) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}The Java solution uses Arrays.sort with a custom comparator defined that uses a mappedValue method to calculate the mapped equivalents for each number. This allows for in-place sorting based on mapped values.
Time Complexity: O(n * k log k), where n is the number of elements and k is the average number of digits. Space Complexity: O(1) additional since we sort in-place.
Approach 3: 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.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array nums.
function sortJumbled(mapping: number[], nums: number[]): number[] {
const n = nums.length;
const f = (x: number): number => {
if (x === 0) {
return mapping[0];
}
let y = 0;
for (let k = 1; x; x = (x / 10) | 0) {
const v = mapping[x % 10];
y += v * k;
k *= 10;
}
return y;
};
const arr: number[][] = nums.map((x, i) => [f(x), i]);
arr.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));
return arr.map(x => nums[x[1]]);
}public class Solution {
public int[] SortJumbled(int[] mapping, int[] nums) {
Func<int, int> f = (int x) => {
if (x == 0) {
return mapping[0];
}
int y = 0;
int k = 1;
int num = x;
while (num != 0) {
int v = mapping[num % 10];
y = k * v + y;
k *= 10;
num /= 10;
}
return y;
};
int n = nums.Length;
List<(int, int)> arr = new List<(int, int)>();
for (int i = 0; i < n; ++i) {
arr.Add((f(nums[i]), i));
}
arr.Sort();
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
ans[i] = nums[arr[i].Item2];
}
return ans;
}
}func sortJumbled(mapping []int, nums []int) (ans []int) {
n := len(nums)
f := func(x int) (y int) {
if x == 0 {
return mapping[0]
}
for k := 1; x > 0; x /= 10 {
v := mapping[x%10]
y = k*v + y
k *= 10
}
return
}
arr := make([][2]int, n)
for i, x := range nums {
arr[i] = [2]int{f(x), i}
}
sort.Slice(arr, func(i, j int) bool { return arr[i][0] < arr[j][0] || arr[i][0] == arr[j][0] && arr[i][1] < arr[j][1] })
for _, p := range arr {
ans = append(ans, nums[p[1]])
}
return
}impl Solution {
pub fn sort_jumbled(mapping: Vec<i32>, nums: Vec<i32>) -> Vec<i32> {
let f = |x: i32| -> i32 {
if x == 0 {
return mapping[0];
}
let mut y = 0;
let mut k = 1;
let mut num = x;
while num != 0 {
let v = mapping[(num % 10) as usize];
y = k * v + y;
k *= 10;
num /= 10;
}
y
};
let n = nums.len();
let mut arr: Vec<(i32, usize)> = Vec::with_capacity(n);
for i in 0..n {
arr.push((f(nums[i]), i));
}
arr.sort();
let mut ans: Vec<i32> = Vec::with_capacity(n);
for (_, i) in arr {
ans.push(nums[i]);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Mapping and Sorting Using Tuples | Time Complexity: O(n * k log k), where n is the number of elements in 'nums' and k is the average number of digits in the numbers. This complexity arises from mapping each digit (O(k)) and sorting (O(n log n)). |
| Approach 2: In-place Reordering Using Custom Comparator | Time Complexity: O(n * k log k), where n is the number of elements and k is the average number of digits. Space Complexity: O(1) additional since we sort in-place. |
| Custom Sorting | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Sort the Jumbled Numbers easy or hard?
Sort the Jumbled Numbers is rated Medium because the main challenge is designing a correct digit transformation and ensuring stable sorting behavior. The algorithm itself is straightforward once the mapping logic is implemented.
Sort the Jumbled Numbers Python/Java solution
Python solutions typically compute mapped values and sort using a key function or tuples. Java implementations often use a custom Comparator to transform digits during comparison. Both approaches run in O(n log n) time.
How to solve Sort the Jumbled Numbers in O(n)?
An O(n) solution is generally not feasible because the final step requires ordering numbers based on mapped values, which typically needs comparison-based sorting. Since mapped numbers can be large and arbitrary, standard solutions rely on O(n log n) sorting rather than linear-time techniques.
What is the best approach for Sort the Jumbled Numbers?
The most practical approach maps each number to its transformed value using the digit mapping and then sorts using tuples like (mappedValue, index, number). This guarantees stable ordering and keeps the logic simple. The time complexity is O(n log n) due to sorting, with O(n) extra space.
Is Sort the Jumbled Numbers asked at Google/Amazon/Meta?
Variants of custom sorting and digit mapping problems appear in interviews at companies like Google and Amazon. The question tests understanding of sorting with custom keys, stable ordering, and digit manipulation within arrays.
What data structure is used in Sort the Jumbled Numbers?
The core structure is an array combined with sorting. Many solutions also use tuples or pairs to store mapped values alongside original indices. This helps maintain stable ordering when two numbers produce the same mapped value.
What is the time complexity of Sort the Jumbled Numbers?
The dominant operation is sorting the array, which takes O(n log n). Computing the mapped value for each number requires processing its digits, adding an O(d) cost per element. Overall complexity is O(n log n) time with O(n) auxiliary space in the tuple approach.