2191. Sort the Jumbled Numbers

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

Approach 01

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
        vector<int> sortedNums;
        vector<tuple<int, int, int>> mappedNums; // (mappedValue, originalIndex, originalValue)

        // Map each number to its corresponding value and store with its index
        // and original value
        for (int i = 0; i < nums.size(); ++i)
            mappedNums.emplace_back(getMappedValue(nums[i], mapping), i, nums[i]);

        // Sort the mapped numbers
        ranges::sort(mappedNums);

        // Collect the original numbers in sorted order
        for (const auto& [mappedValue, index, originalValue] : mappedNums)
            sortedNums.push_back(originalValue);

        return sortedNums;
    }

private:
    // Function to get the mapped value of a number based on the provided
    // mapping
    int getMappedValue(int num, const vector<int>& mapping) {
        string mappedString;
        for (const char c : to_string(num))
            mappedString += to_string(mapping[c - '0']);
        return stoi(mappedString);
    }
};

from typing import List, Tuple

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        mappedNums = []  # List to store (mappedValue, originalIndex, originalValue)

        # Map each number to its corresponding value and store with its index and original value
        for i, num in enumerate(nums):
            mappedValue = self.getMappedValue(num, mapping)
            mappedNums.append((mappedValue, i, num))

        # Sort the mapped numbers
        mappedNums.sort()

        # Collect the original numbers in sorted order
        sortedNums = [originalValue for mappedValue, index, originalValue in mappedNums]

        return sortedNums

    # Function to get the mapped value of a number based on the provided mapping
    def getMappedValue(self, num: int, mapping: List[int]) -> int:
        mappedString = ''.join(str(mapping[int(digit)]) for digit in str(num))
        return int(mappedString)

Time Complexity

• Mapping Values:

  Iterating through the nums vector to map each number to its corresponding value takes \( O(n) \) time, where \( n \) is the number of elements in nums. Each number is converted to a string and mapped, which involves operations proportional to the number of digits in the number. In the worst case, the time complexity for this operation is still \( O(n \cdot d) \), where \( d \) is the maximum number of digits in any number in nums.

• Sorting:

  Sorting the mappedNums vector, which contains \( n \) elements, takes \( O(n \log n) \) time.

• Collecting Original Numbers:

  Iterating through the sorted mappedNums vector to collect the original numbers takes \( O(n) \) time.

• Overall Time Complexity:

  The overall time complexity is dominated by the sorting step, resulting in \( O(n \log n) \). The mapping step, which includes converting numbers to strings, is linear but could be factored into the constant factor of \( O(n) \) in practice.

Space Complexity

• Auxiliary Space:

  The space used for the mappedNums vector is \( O(n) \) as it stores tuples of mapped values, original indices, and original values. The space used for sortedNums is also \( O(n) \), as it stores the final sorted numbers.

• Additional Space:

  The space used for temporary variables such as mappedString in the getMappedValue function is minimal compared to the overall space complexity.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \), where \( n \) is the number of elements in the nums vector.

Approach 02

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
        vector<int> sortedNums;
        map<int, vector<int>> mappedToOriginalNums; // Map to store mapped value to original numbers

        // Map each number to its corresponding value and store in a map
        for (const int num : nums)
            mappedToOriginalNums[getMappedValue(num, mapping)].push_back(num);

        // Collect the original numbers in sorted order of their mapped values
        for (const auto& [mappedValue, originalNums] : mappedToOriginalNums)
            sortedNums.insert(sortedNums.end(), originalNums.begin(),
                              originalNums.end());

        return sortedNums;
    }

private:
    // Function to get the mapped value of a number based on the provided mapping
    int getMappedValue(int num, const vector<int>& mapping) {
        string mappedString;
        for (const char c : to_string(num))
            mappedString += to_string(mapping[c - '0']);
        return stoi(mappedString);
    }
};

from typing import List, Dict
from collections import defaultdict

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        sortedNums = []
        mappedToOriginalNums = defaultdict(list)  # Dictionary to store mapped value to original numbers

        # Map each number to its corresponding value and store in a dictionary
        for num in nums:
            mappedValue = self.getMappedValue(num, mapping)
            mappedToOriginalNums[mappedValue].append(num)

        # Collect the original numbers in sorted order of their mapped values
        for mappedValue in sorted(mappedToOriginalNums.keys()):
            sortedNums.extend(mappedToOriginalNums[mappedValue])

        return sortedNums

    # Function to get the mapped value of a number based on the provided mapping
    def getMappedValue(self, num: int, mapping: List[int]) -> int:
        mappedString = ''.join(str(mapping[int(digit)]) for digit in str(num))
        return int(mappedString)

Time Complexity

• Mapping Each Number:

  The function getMappedValue is called for each number in the input vector nums. Converting each number to a string and then applying the mapping takes \( O(d) \) time per number, where \( d \) is the number of digits in the number. Since there are \( n \) numbers, the total time for mapping is \( O(n \cdot d) \).

• Storing Mapped Values in Map:

  Inserting each number into the map mappedToOriginalNums takes \( O(\log n) \) time on average due to the nature of maps (balanced binary trees). Thus, storing all \( n \) numbers in the map results in \( O(n \log n) \) time.

• Collecting Sorted Numbers:

  Collecting the sorted numbers from the map involves iterating over all entries in the map and inserting each number into sortedNums. This operation takes \( O(n) \) time, assuming the total number of elements is \( n \).

• Overall Time Complexity:

  The overall time complexity is \( O(n \cdot d + n \log n) \), where \( n \) is the number of elements in the input vector and \( d \) is the number of digits in the numbers.

Space Complexity

• Auxiliary Space:

  The space complexity is mainly due to the map mappedToOriginalNums and the vector sortedNums. The map stores \( n \) numbers, and the vector sortedNums stores the same numbers, leading to \( O(n) \) space usage for both combined.

• String Conversion:

  The string conversion in the getMappedValue function uses \( O(d) \) space for each number, but this is done sequentially, so the overall space complexity remains \( O(d) \).

• Overall Space Complexity:

  The overall space complexity is \( O(n) \), where \( n \) is the number of elements in the input vector.