Scale Engineer

Sort the Jumbled Numbers

Med
#1996Time: O(N * log(N) * D), where `N` is the number of elements in `nums` and `D` is the maximum number of digits in a number from `nums`. The sort takes `O(N * log(N))` comparisons. Each comparison involves two calls to `getMappedValue`, which takes `O(D)` time.Space: O(N + D). `O(N)` is required to store the list of numbers. `O(D)` is used for the string builder within the `getMappedValue` function. The sort itself (Timsort) can take up to `O(N)` space in the worst case.
Algorithms
Sorting
Data structures
Array

Prompt

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.

 

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 == 10
  • 0 <= mapping[i] <= 9
  • All the values of mapping[i] are unique.
  • 1 <= nums.length <= 3 * 104
  • 0 <= nums[i] < 109

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves using a standard sorting algorithm with a custom comparator. The comparator calculates the mapped value for two numbers on the fly during each comparison. Because comparison-based sorting algorithms like Timsort (used by Collections.sort) compare elements multiple times, the mapped value for a single number will be computed repeatedly, leading to poor performance.

Algorithm

  • Convert the input int[] nums to a List<Integer> to leverage Java's stable Collections.sort.
  • Define a helper function getMappedValue(num, mapping) that:
    • Converts num to its string representation.
    • Iterates through each character (digit) of the string.
    • Replaces the digit with its mapped value from the mapping array.
    • Builds a new string with the mapped digits.
    • Parses the new string back to a number. It's safer to parse to a long to avoid potential overflow, though an int might suffice given the constraints.
  • Sort the list using Collections.sort with a custom comparator.
  • The comparator takes two numbers, a and b, calls getMappedValue for both, and compares the results.
  • Copy the elements from the sorted list back to an int[] array.
  • Return the result array.

Walkthrough

The core of this method is a custom comparison logic that we provide to a sorting function. First, we need a helper function, let's call it getMappedValue, which takes an integer, converts it to a string, replaces each digit character according to the mapping array, and then parses the resulting string back to an integer. For example, if num = 991 and mapping[9]=6, mapping[1]=9, getMappedValue(991) would convert 991 to "991", map it to "669", and return the integer 669.

Since standard sorts on primitive arrays (like int[]) in Java are not guaranteed to be stable, we first convert the nums array into a List<Integer>. We then use Collections.sort() on this list, providing a lambda expression as the comparator. This comparator (a, b) -> ... will call getMappedValue(a) and getMappedValue(b) and compare the results. Collections.sort() is a stable sort, which satisfies the problem's requirement for elements with equal mapped values.

Finally, the sorted list is converted back into an int[] array. The main drawback is the performance hit from re-calculating mapped values. A number might be part of O(log N) comparisons, leading to O(log N) calculations of its mapped value.

class Solution {    public int[] sortJumbled(int[] mapping, int[] nums) {        List<Integer> numsList = new ArrayList<>();        for (int num : nums) {            numsList.add(num);        }         // Sort using a custom comparator that calculates mapped values on the fly        Collections.sort(numsList, (a, b) -> {            long mappedA = getMappedValue(a, mapping);            long mappedB = getMappedValue(b, mapping);            return Long.compare(mappedA, mappedB);        });         int[] result = new int[nums.length];        for (int i = 0; i < nums.length; i++) {            result[i] = numsList.get(i);        }        return result;    }     private long getMappedValue(int n, int[] mapping) {        char[] s = Integer.toString(n).toCharArray();        for (int i = 0; i < s.length; i++) {            s[i] = (char) (mapping[s[i] - '0'] + '0');        }        return Long.parseLong(new String(s));    }}

Complexity

Time

O(N * log(N) * D), where `N` is the number of elements in `nums` and `D` is the maximum number of digits in a number from `nums`. The sort takes `O(N * log(N))` comparisons. Each comparison involves two calls to `getMappedValue`, which takes `O(D)` time.

Space

O(N + D). `O(N)` is required to store the list of numbers. `O(D)` is used for the string builder within the `getMappedValue` function. The sort itself (Timsort) can take up to `O(N)` space in the worst case.

Trade-offs

Pros

  • Relatively simple to understand and implement using standard library functions.

  • Code is concise.

Cons

  • Inefficient due to redundant computations of mapped values. The mapped value for a single number is recalculated every time it's involved in a comparison during the sort.

Solutions

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;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem