2191. Sort the Jumbled Numbers

MediumArraySorting
Leetcode Link

Problem Description

The problem presents a scenario where we have a custom mapping for digits from 0 to 9, implying a shuffled decimal system. This mapping is given as an array where mapping[i] = j means the digit i should be mapped to digit j. For example, if mapping[1] = 5, every 1 in any number will be treated as 5. The task is to transform a list of integers (nums) according to this new digit mapping, and then sort the list based on the new "mapped" values.

After the transformation, the sorted list should maintain the order of numbers that have the same mapped value as they appear in the original nums list. It is important to note that while the sorting is done based on the mapped values, the final sorted list should contain the original numbers, not their mapped counterparts.

Intuition

The intuition behind the implemented solution is to simulate this new decimal system by creating a corresponding mapped value for each number in the given list nums. The first step is to convert each number to its mapped value according to the provided mapping. This means replacing each digit of the number with its correspondent in the mapping.

While creating these mapped values, we have to handle them carefully to retain the original order of numbers. Hence, for each number in nums, we pair it with its index in the array; that way, after sorting the numbers by their mapped values, we can still return the original numbers in their new sorted order.

The next step is to sort these pairs (which contain the mapped value and the original index) by the mapped value. If this results in ties (i.e., two numbers having the same mapped value), the relative order of their indices will resolve which should come first, achieving "stable sorting."

Finally, we reconstruct the sorted list of original numbers by taking the second element from each sorted pair, which is the original index of that number in the nums array.

Note that the way the mapped values are computed respects the magnitude of each digit in the original number (i.e., the tens place is still the tens place after mapping, the hundreds place is still the hundreds place, and so forth). This means we have to multiply the mapped digit by its place value (k) as we form the new number y. The k value is started at 1 and is multiplied by 10 for each digit we move to the left.

After all mapped values and their original indices are sorted, we can then create and return a list of the original numbers from nums by their order determined by the mapped values.

Learn more about Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

Solution Approach

The solution provided follows a mapping and sorting approach to achieve the final sorted array based on custom mapped values.

Firstly, the solution leverages a list called arr to store tuples. Each tuple contains two values: the mapped value of the number and the original index of the number in the nums array.

Here is a step-by-step breakdown of the algorithm:

  1. Iterate through each number in the nums array with its index. For each number x and its index i:

    • Initialize a variable y to be the mapped value of 0. This variable will accumulate the final mapped number. Note that if x is zero, we set y to mapping[0] as its mapped value.
    • Initialize a variable k which represents the current digit's place value (e.g., 1 for units, 10 for tens, etc.).

  2. For each digit v in the number x (obtained by repeatedly using divmod to split off the last digit):

    • Calculate the mapped digit by using the given mapping (i.e., mapping[v]).
    • Multiply the mapped digit by its current place value k and add it to y, building up the new mapped number digit by digit.
    • Multiply k by 10 to update the place value for the next digit to the left.

  3. After finishing the mapping for a number, append a tuple (y, i) to the list arr, where y is the mapped value obtained and i is the index of the number in nums.

  4. Sort the list arr by the first tuple element, which is the mapped value. Python's default sorting algorithm is stable, which guarantees that arr will be sorted by y but maintain the relative order of elements that have the same y value.

  5. Create the final sorted list by extracting and appending the original numbers from nums using the sorted indices found in arr: [nums[i] for _, i in arr].

The overall time complexity of the solution is dominated by the sorting step, which is O(n log n), where n is the length of the nums array. The space complexity is O(n) due to the additional list arr used for sorting purposes.

This solution pattern effectively applies a custom sort key defined by a map, which is a common way to sort elements in a non-standard manner while maintaining stability in sorting.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Let's consider an example to walk through the solution approach. Suppose we have a mapping array and a list of numbers as follows:

  • mapping = [2, 1, 4, 3, 6, 5, 8, 7, 0, 9]
  • nums = [990, 332, 981]

Based on the mapping, each digit in the numbers from nums should be converted as follows:

  • '0' maps to '2'
  • '1' maps to '1'
  • '2' maps to '4'
  • '3' maps to '3'
  • '4' maps to '6'
  • '5' maps to '5'
  • '6' maps to '8'
  • '7' maps to '7'
  • '8' maps to '0'
  • '9' maps to '9'

  1. We'll initiate the list arr to store tuples of the mapped value and the original index.

  2. We start iterating through nums. For 990, its index i is 0:

    • Mapping '9' to '9' and '0' to '2', the mapped value of 990 is 992.
    • Append to arr the tuple (992, 0).

  3. Next, for 332, its index i is 1:

    • Mapping '3' to '3' and '2' to '4', the mapped value of 332 is 334.
    • Append to arr the tuple (334, 1).

  4. Lastly, for 981, its index i is 2:

    • Mapping '9' to '9', '8' to '0', and '1' to '1', the mapped value of 981 is 901.
    • Append to arr the tuple (901, 2).

Now arr looks like this: [(992, 0), (334, 1), (901, 2)].

  1. We sort arr using the first element of the tuples, so the list becomes [(901, 2), (334, 1), (992, 0)].

  2. After sorting, we create the final sorted list based on the original indices: [nums[i] for _, i in arr]. Using the sorted indices, we get nums[2], nums[1], nums[0], which correspond to the numbers [981, 332, 990].

So, the transformed and sorted list is [981, 332, 990] based on the new "mapped" values, yet the numbers themselves retain their original form.

Solution Implementation

1class Solution:
2    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
3        # List to hold tuples of the mapped value and its original index
4        mapped_with_index = []
5      
6        # Iterate over the input numbers' list
7        for index, num in enumerate(nums):
8            # If the number is 0, get the mapped value for 0, else start with 0
9            mapped_num = mapping[0] if num == 0 else 0
10            power_of_ten = 1  # To keep track of the decimal place
11          
12            # Decompose the number into digits and map using the provided mapping
13            while num:
14                num, digit = divmod(num, 10)
15                # Map the digit, adjust decimal place and add to the mapped number
16                mapped_num = mapping[digit] * power_of_ten + mapped_num
17                power_of_ten *= 10  # Increase the decimal place
18          
19            # Append the tuple of mapped number and original index to the list
20            mapped_with_index.append((mapped_num, index))
21      
22        # Sort the list according to the mapped numbers, stable for identical values
23        mapped_with_index.sort()
24      
25        # Reconstruct the sorted list using the original indices
26        return [nums[i] for _, i in mapped_with_index]
27
1import java.util.Arrays;
2
3class Solution {
4  
5    // Method to sort the array nums based on a custom mapping.
6    public int[] sortJumbled(int[] mapping, int[] nums) {
7        // Get the length of the nums array.
8        int n = nums.length;
9      
10        // Create a 2D array to store the mapped number and the original index.
11        int[][] mappedWithIndex = new int[n][2];
12      
13        // Iterate over the array of numbers.
14        for (int i = 0; i < n; ++i) {
15            int originalNum = nums[i];   // Original number from nums.
16            int mappedNum = originalNum == 0 ? mapping[0] : 0;  // Map the number based on mapping rules.
17            int placeValue = 1;   // To reconstruct the mapped number based on individual digits.
18          
19            // Map each digit of the original number based on the 'mapping' array.
20            while (originalNum > 0) {
21                int digit = originalNum % 10;  // Retrieve the last digit.
22                mappedNum += placeValue * mapping[digit];  // Map the digit and add to mappedNum considering the place value.
23                placeValue *= 10;  // Move to the next place value (tens, hundreds, etc.).
24                originalNum /= 10;  // Drop the last digit.
25            }
26          
27            // Store the mapped number and the original index in the array.
28            mappedWithIndex[i] = new int[] {mappedNum, i};
29        }
30      
31        // Sort the array 'mappedWithIndex' based on the mapped numbers and indices.
32        Arrays.sort(mappedWithIndex, (a, b) -> 
33            a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); // If mapped numbers are equal, compare index.
34      
35        // Prepare the final sorted array based on the mapped values.
36        int[] sortedArray = new int[n];
37        for (int i = 0; i < n; ++i) {
38            sortedArray[i] = nums[mappedWithIndex[i][1]];
39        }
40      
41        // Return the sorted array.
42        return sortedArray;
43    }
44}
45
1class Solution {
2public:
3    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
4        int numsSize = nums.size(); // Number of elements in nums
5        vector<pair<int, int>> mappedAndIndexPairs(numsSize); // Pair to store the mapped value and original index
6
7        // Transform each number as per the mapping and associate it with its original index
8        for (int i = 0; i < numsSize; ++i) {
9            int originalNum = nums[i];
10            int mappedNum = originalNum == 0 ? mapping[0] : 0; // If the number is 0, directly map it
11            int placeValue = 1; // Represents the place value in the mapped number
12
13            // Decompose the number into its digits and transform it according to the mapping
14            while (originalNum > 0) {
15                int digit = originalNum % 10; // Get the last digit
16                mappedNum += placeValue * mapping[digit]; // Map the digit and add to the mapped number
17                originalNum /= 10; // Remove the last digit from the original number
18                placeValue *= 10; // Move to the next place value
19            }
20
21            // Save the pair of mapped number and original index
22            mappedAndIndexPairs[i] = {mappedNum, i};
23        }
24
25        // Sort the pairs. The order is firstly by the mapped number, and then by the original index
26        sort(mappedAndIndexPairs.begin(), mappedAndIndexPairs.end());
27
28        // Extract the numbers from the sorted pairs, preserving the new order
29        vector<int> sortedNums;
30        for (auto& pair : mappedAndIndexPairs) {
31            sortedNums.push_back(nums[pair.second]);
32        }
33
34        // Return the sorted numbers as per the jumbled mapping order
35        return sortedNums;
36    }
37};
38
1function sortJumbled(mapping: number[], nums: number[]): number[] {
2    const numsLength = nums.length;
3    const mappedNums: number[][] = [];
4
5    // Loop through all numbers in the 'nums' array
6    for (let i = 0; i < numsLength; ++i) {
7        let originalNum = nums[i];
8        // Calculate the mapped value of an individual number
9        // If the number is zero, map it directly using the mapping array;
10        // else initialize it to zero to build upon
11        let mappedValue = originalNum === 0 ? mapping[0] : 0;
12        let positionMultiplier = 1; // Used to place the digit at the correct position
13
14        // Decompose the number and map its digits using the given mapping
15        for (; originalNum > 0; originalNum = Math.floor(originalNum / 10), positionMultiplier *= 10) {
16            // Add the mapped digit multiplied by its positional value to 'mappedValue'
17            mappedValue += mapping[originalNum % 10] * positionMultiplier;
18        }
19
20        // Store the mapped value along with the original index
21        mappedNums.push([mappedValue, i]);
22    }
23
24    // Sort the 'mappedNums' array based on the mapped values, and if those are equal, by the original indices
25    mappedNums.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));
26
27    // Map the sorted array back to the original numbers using their stored indices
28    return mappedNums.map(mappedPair => nums[mappedPair[1]]);
29}
30
Not Sure What to Study? Take the 2-min Quiz：

Which of the following uses divide and conquer strategy?

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by a few factors:

  1. Iterating over each element in nums: O(N), where N is the number of elements in nums.
  2. Within the loop, transforming each number based on the mapping. In the worst case, the number of digits D in a number is proportional to the logarithm of the number (log10(x)), resulting in a complexity of O(D). Since D is small compared to N for a reasonable range of integers, this can be approximated to O(log(M)), where M is the maximum number in nums.
  3. Sorting the transformed array, which would take O(N log N) time.

Thus, combining these factors, the overall time complexity is O(N * log(M) + N log N). If N is much larger than M, the dominant term is O(N log N).

Space Complexity

The space complexity of the code involves:

  1. The additional array arr used to store the transformed tuples, which adds a space complexity of O(N).

There are no other significant uses of additional space, so the total space complexity is O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫