✅💯🔥Explanations No One Will Give You🎓🎯Very Detailed Approach🔥Extremely Simple And Beats 100%🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nProblem Overview\n- You are given a mapping array that defines a mapping rule for digit
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n***Problem Overview***\n- You are given a mapping array that defines a mapping rule for digits 0 to 9. For example, if mapping[1] = 5, it means that the digit \'1\' should be replaced with \'5\' in the mapped value. You need to sort an array nums based on the integers formed by applying this mapping to each number, without actually replacing the numbers in the sorted output.\n\n***The solution involves the following steps:***\n\n- Mapping Transformation: For each number in nums, convert it to its mapped value using the mapping array. This means replacing each digit of the number with its corresponding digit from mapping.\n\n- Pairing and Sorting: Create pairs of the form (mapped value, original index) for each number in nums.\n- Sort these pairs based on the mapped values. If two mapped values are the same, the original indices ensure stability (i.e., original relative order is maintained).\n\n- Extract Sorted Results: Extract the numbers from nums based on the sorted pairs of mapped values.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Helper Function makeNum:\n\n- This recursive function takes an integer n and converts it to its mapped value using the mapping array.\n- For a given digit n % 10, it fetches the mapped digit and then recursively processes the remaining digits (n / 10).\n- Example: For n = 123 and mapping = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], it will transform 123 to 123 as each digit maps to itself.\nMain Function sortJumbled:\n\n2. Initialize two vectors: ans to store the sorted results, and vec to store pairs of (mapped value, original index).\n- For each number in nums: If the number is 0, directly use mapping[0] as the mapped value.\n- Otherwise, use makeNum to get the mapped value.\n- Store the pair (mapped value, original index) in vec.\n- Sort vec based on the mapped values. The default sort maintains the original relative order for equal values.\n- Extract the sorted numbers from nums using the indices stored in vec and store them in ans.\n\n# Complexity\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Converting each number to its mapped value takes O(d) time, where d is the number of digits in the number. For n numbers, this becomes O(n * d).\n- Sorting the vec vector takes O(n log n).\n- The overall time complexity is O(n * d + n log n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- The space complexity is primarily due to the vec vector, which stores n pairs, making it O(n).\n- The auxiliary space for recursion in makeNum is bounded by the number of digits, which is a small constant compared to n.\n\n\n***PLEASE GIVE AN UPVOTE IF YOU LIKED THE EXPLAINATION\u2B50\u2B50\u2B50\u2B50\u2B50***\n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {\n        int numsSize = nums.size(); // Number of elements in nums\n        vector<pair<int, int>> mappedAndIndexPairs(numsSize); // Pair to store the mapped value and original index\n\n        // Transform each number as per the mapping and associate it with its original index\n        for (int i = 0; i < numsSize; ++i) {\n            int originalNum = nums[i];\n            int mappedNum = originalNum == 0 ? mapping[0] : 0; // If the number is 0, directly map it\n            int placeValue = 1; // Represents the place value in the mapped number\n\n            // Decompose the number into its digits and transform it according to the mapping\n            while (originalNum > 0) {\n                int digit = originalNum % 10; // Get the last digit\n                mappedNum += placeValue * mapping[digit]; // Map the digit and add to the mapped number\n                originalNum /= 10; // Remove the last digit from the original number\n                placeValue *= 10; // Move to the next place value\n            }\n\n            // Save the pair of mapped number and original index\n            mappedAndIndexPairs[i] = {mappedNum, i};\n        }\n\n        // Sort the pairs. The order is firstly by the mapped number, and then by the original index\n        sort(mappedAndIndexPairs.begin(), mappedAndIndexPairs.end());\n\n        // Extract the numbers from the sorted pairs, preserving the new order\n        vector<int> sortedNums;\n        for (auto& pair : mappedAndIndexPairs) {\n            sortedNums.push_back(nums[pair.second]);\n        }\n\n        // Return the sorted numbers as per the jumbled mapping order\n        return sortedNums;\n    }\n};\n```\n```JAVA []\nclass Solution {\n    public int[] sortJumbled(int[] mapping, int[] nums) {\n        int numsSize = nums.length; // Number of elements in nums\n        List<Pair> mappedAndIndexPairs = new ArrayList<>(); // List to store the mapped value and original index\n\n        // Transform each number as per the mapping and associate it with its original index\n        for (int i = 0; i < numsSize; ++i) {\n            int originalNum = nums[i];\n            int mappedNum = originalNum == 0 ? mapping[0] : 0; // If the number is 0, directly map it\n            int placeValue = 1; // Represents the place value in the mapped number\n\n            // Decompose the number into its digits and transform it according to the mapping\n            while (originalNum > 0) {\n                int digit = originalNum % 10; // Get the last digit\n                mappedNum += placeValue * mapping[digit]; // Map the digit and add to the mapped number\n                originalNum /= 10; // Remove the last digit from the original number\n                placeValue *= 10; // Move to the next place value\n            }\n\n            // Save the pair of mapped number and original index\n            mappedAndIndexPairs.add(new Pair(mappedNum, i));\n        }\n\n        // Sort the pairs. The order is firstly by the mapped number, and then by the original index\n        Collections.sort(mappedAndIndexPairs, (a, b) -> {\n            if (a.mappedNum != b.mappedNum) {\n                return Integer.compare(a.mappedNum, b.mappedNum);\n            } else {\n                return Integer.compare(a.index, b.index);\n            }\n        });\n\n        // Extract the numbers from the sorted pairs, preserving the new order\n        int[] sortedNums = new int[numsSize];\n        for (int i = 0; i < numsSize; ++i) {\n            sortedNums[i] = nums[mappedAndIndexPairs.get(i).index];\n        }\n\n        // Return the sorted numbers as per the jumbled mapping order\n        return sortedNums;\n    }\n\n    // Helper class to store the mapped number and its original index\n    private static class Pair {\n        int mappedNum;\n        int index;\n\n        Pair(int mappedNum, int index) {\n            this.mappedNum = mappedNum;\n            this.index = index;\n        }\n    }\n}\n\n```\n```python []\nclass Solution:\n    def sortJumbled(self, mapping, nums):\n        numsSize = len(nums)  # Number of elements in nums\n        mappedAndIndexPairs = []  # List to store the mapped value and original index\n\n        # Transform each number as per the mapping and associate it with its original index\n        for i in range(numsSize):\n            originalNum = nums[i]\n            mappedNum = mapping[0] if originalNum == 0 else 0  # If the number is 0, directly map it\n            placeValue = 1  # Represents the place value in the mapped number\n\n            # Decompose the number into its digits and transform it according to the mapping\n            while originalNum > 0:\n                digit = originalNum % 10  # Get the last digit\n                mappedNum += placeValue * mapping[digit]  # Map the digit and add to the mapped number\n                originalNum //= 10  # Remove the last digit from the original number\n                placeValue *= 10  # Move to the next place value\n\n            # Save the pair of mapped number and original index\n            mappedAndIndexPairs.append((mappedNum, i))\n\n        # Sort the pairs. The order is firstly by the mapped number, and then by the original index\n        mappedAndIndexPairs.sort()\n\n        # Extract the numbers from the sorted pairs, preserving the new order\n        sortedNums = [nums[i] for _, i in mappedAndIndexPairs]\n\n        # Return the sorted numbers as per the jumbled mapping order\n        return sortedNums\n\n```\n```python3 []\nclass Solution:\n    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:\n        numsSize = len(nums)  # Number of elements in nums\n        mappedAndIndexPairs = []  # List to store the mapped value and original index\n\n        # Transform each number as per the mapping and associate it with its original index\n        for i in range(numsSize):\n            originalNum = nums[i]\n            mappedNum = mapping[0] if originalNum == 0 else 0  # If the number is 0, directly map it\n            placeValue = 1  # Represents the place value in the mapped number\n\n            # Decompose the number into its digits and transform it according to the mapping\n            while originalNum > 0:\n                digit = originalNum % 10  # Get the last digit\n                mappedNum += placeValue * mapping[digit]  # Map the digit and add to the mapped number\n                originalNum //= 10  # Remove the last digit from the original number\n                placeValue *= 10  # Move to the next place value\n\n            # Save the pair of mapped number and original index\n            mappedAndIndexPairs.append((mappedNum, i))\n\n        # Sort the pairs. The order is firstly by the mapped number, and then by the original index\n        mappedAndIndexPairs.sort()\n\n        # Extract the numbers from the sorted pairs, preserving the new order\n        sortedNums = [nums[i] for _, i in mappedAndIndexPairs]\n\n        # Return the sorted numbers as per the jumbled mapping order\n        return sortedNums\n\n```\n\n
['Array', 'Sorting', 'Python', 'C++', 'Java', 'Python3']