Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: 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 nums should only be sorted based on their mapped values and not be replaced by them.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[8,9,4,0,2,1,3,5,7,6] [991,338,38]
[0,1,2,3,4,5,6,7,8,9] [789,456,123]
map-sum-pairs)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2191: Sort the Jumbled Numbers
class Solution {
private int[] mapping;
public int[] sortJumbled(int[] mapping, int[] nums) {
this.mapping = mapping;
int n = nums.length;
int[][] arr = new int[n][0];
for (int i = 0; i < n; ++i) {
arr[i] = new int[] {f(nums[i]), i};
}
Arrays.sort(arr, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
ans[i] = nums[arr[i][1]];
}
return ans;
}
private int f(int x) {
if (x == 0) {
return mapping[0];
}
int y = 0;
for (int k = 1; x > 0; x /= 10) {
int v = mapping[x % 10];
y = k * v + y;
k *= 10;
}
return y;
}
}
// Accepted solution for LeetCode #2191: Sort the Jumbled Numbers
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
}
# Accepted solution for LeetCode #2191: Sort the Jumbled Numbers
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]
// Accepted solution for LeetCode #2191: Sort the Jumbled Numbers
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
}
}
// Accepted solution for LeetCode #2191: Sort the Jumbled Numbers
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]]);
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.