Most intuitive approach💡 || Detailed explanation with image visualization✨ || Beginner friendly🚀
Overview\n\nWe are given an integer array mapping containing 10 unique values from 0 to 9 and an integer nums containing at most 30000 integers.\n\nThe mapped v
# Overview\n\nWe are given an integer array `mapping` containing 10 unique values from `0` to `9` and an integer `nums` containing at most `30000` integers.\n\nThe mapped value of an integer is given by replacing the index with the value of `mapping` at that index (zero-based indexing). For example, if `mapped` is `[0,9,8,7,6,5,4,3,2,1]` then the mapped value of `123` is `987`.\n\nWe need to return the array `nums` sorted in the non-decreasing order based on the mapped values of its elements. These values should not be the mapped values.\n\n> Note: Elements with the same mapped values should be arranged in the same relative order as `nums`.\n\n* * *\n\n# Approach 1: Conversion using strings and Sorting\n\n## Intuition\n\nObserve that we need to replace every digit of all elements in `nums` with the digits of the `mapping` array. Since the data type for `nums` is an integer, we might find it difficult to make the updates directly on a particular digit of the integer. If we convert this integer to a string, we can directly convert any character of this integer to the desired character in constant time.\n\nAfter making the changes, we can convert the mapped string to an integer and push it into an array. But, what if there are equal mapped values for two strings? Then, we need to sort them according to their indices. So, we create an array of pairs that stores the mapped integer value and its index.\n\nSort the array of pairs in non-decreasing order using any stable sorting algorithm. By default, C++, Java, and Python use stable sorting algorithms. Therefore, the first value of every pair is sorted in non-decreasing order. If these values are equal, the array is sorted in the non-decreasing order of the index values. Store the values of `nums` at these sorted indices and return them.\n\n#### Algorithm\n\n1.  Initialize an array of pairs given by `storePairs`.\n2.  Iterate `i` through the `nums` array:\n    -   Store a string `number` as the string conversion of the integer `nums[i]`.\n    -   Initialize an empty string `formed`.\n    -   Iterate `j` through the string `number`:\n        -   Append the mapping of the current character of `number` to `formed`.\n    -   Convert the string `formed` to an integer `mappedValue`.\n    -   Push the pair `mappedValue` and the current index `i` in `storePairs`.\n3.  Sort the `storePairs` array.\n4.  Create an array `answer`.\n5.  Iterate through `storePairs` and append the `nums` value at the index to the `answer`.\n6.  Return the `answer` array.\n\n## Image visualization\n![3c7efdfe-1750-4e2b-8fa0-b2e77700a931.png](https://assets.leetcode.com/users/images/f6b578cf-d982-4dbb-87f7-e3e5d611ff9e_1721813872.56416.png)\n\n![78a37da1-e8d2-4930-9f90-a6b070371f80.png](https://assets.leetcode.com/users/images/2904d829-e645-4dcf-a527-d712ca474c76_1721813904.6093705.png)\n\n![4f77a1cb-f813-470e-ae22-e781c020b41e.png](https://assets.leetcode.com/users/images/d2bfb12d-7382-46c4-a5ca-328104430bde_1721813893.3937645.png)\n\n\n![dd5d2697-b0fd-4dd2-aaa5-dcb26720aa3f.png](https://assets.leetcode.com/users/images/fe0ad0e0-5963-42cc-a0ce-d8e0da291722_1721813919.6330662.png)\n\n![99ac3adb-b584-4313-a9e9-f4fb10ad1ee4.png](https://assets.leetcode.com/users/images/619acd26-9e85-4062-9c4e-785305220170_1721813929.612713.png)\n\n![9db34eec-4095-4fb0-85f9-8a088cc6d646.png](https://assets.leetcode.com/users/images/ad3622bc-02e9-4c45-a923-858632e0b580_1721813941.721261.png)\n\n\n\n## Implementation\n\n```java []\nclass Solution {\n\n    public int[] sortJumbled(int[] mapping, int[] nums) {\n        ArrayList<Integer[]> storePairs = new ArrayList<>();\n\n        for (int i = 0; i < nums.length; ++i) {\n            // Convert current value to string\n            String number = Integer.toString(nums[i]);\n            String formed = "";\n            for (int j = 0; j < number.length(); ++j) {\n                formed = formed +\n                Integer.toString(mapping[number.charAt(j) - \'0\']);\n            }\n            // Store the mapped value.\n            int mappedValue = Integer.parseInt(formed);\n            // Push a pair consisting of mapped value and original value\'s index.\n            storePairs.add(new Integer[] { mappedValue, i });\n        }\n\n        // Sort the array in non-decreasing order by the first value (default).\n        Collections.sort(\n            storePairs,\n            new Comparator<Integer[]>() {\n                @Override\n                public int compare(Integer[] o1, Integer[] o2) {\n                    return o1[0].compareTo(o2[0]);\n                }\n            }\n        );\n\n        int[] answer = new int[nums.length];\n        for (int i = 0; i < storePairs.size(); i++) {\n            answer[i] = nums[storePairs.get(i)[1]];\n        }\n        return answer;\n    }\n}\n```\n```python []\nclass Solution:\n    def sortJumbled(self, mapping, nums):\n        store_pairs = []\n\n        for i in range(len(nums)):\n            # Convert current value to string\n            number = str(nums[i])\n            formed = ""\n            for j in range(len(number)):\n                formed = formed + str(mapping[int(number[j])])\n            # Store the mapped value.\n            mapped_value = int(formed)\n            # Push a pair consisting of mapped value and original value\'s index.\n            store_pairs.append((mapped_value, i))\n\n        # Sort the array in non-decreasing order by the first value (default).\n        store_pairs.sort()\n        answer = []\n        for pair in store_pairs:\n            answer.append(nums[pair[1]])\n        return answer\n```\n```c++ []\nclass Solution {\npublic:\n    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {\n        vector<pair<int, int>> storePairs;\n\n        for (int i = 0; i < nums.size(); ++i) {\n            // Convert current value to string\n            string number = to_string(nums[i]);\n            string formed = "";\n            for (int j = 0; j < number.size(); ++j) {\n                formed = formed + (to_string(mapping[number[j] - \'0\']));\n            }\n            // Store the mapped value.\n            int mappedValue = stoi(formed);\n            // Push a pair consisting of mapped value and original value;s\n            // index.\n            storePairs.push_back({mappedValue, i});\n        }\n\n        // Sort the array in non-decreasing order by the first value (default).\n        sort(storePairs.begin(), storePairs.end());\n        vector<int> answer;\n        for (auto pair : storePairs) {\n            answer.push_back(nums[pair.second]);\n        }\n        return answer;\n    }\n};\n```\n\n\n## Complexity Analysis\n\nLet n be the size of the `nums` array.\n\n-   Time complexity:$$ O(n\u22C5logn)$$\n    \n    For every integer in `nums`, we convert it to a string and perform constant operations over its length. The time taken for converting an integer to a string, and vice versa, is O(lengthofinteger) time, which is proportional to the logarithmic value of `n`. Therefore, the time complexity for these operations is given by O(n\u22C5logn).\n    \n    Sorting the array of pairs takes O(n\u22C5logn) time. All other operations are linear or constant time.\n    \n    Therefore, the total time complexity is given by O(n\u22C5logn).\n    \n-   Space complexity: $$O(n)$$\n    \n    We create two new arrays of size `n`. Apart from this, some extra space is used when we sort arrays in place. The space complexity of the sorting algorithm depends on the programming language.\n    \n    -   In Python, the sort method sorts a list using the Timsort algorithm which is a combination of Merge Sort and Insertion Sort and has O(n) additional space.\n    -   In Java, `Arrays.sort()` is implemented using a variant of the Quick Sort algorithm which has a space complexity of O(logn) for sorting two arrays.\n    -   In C++, the `sort()` function is implemented as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worse-case space complexity of O(logn).\n    \n    Therefore, the total space complexity is given by O(n).\n    \n\n* * *\n\n# Approach 2: Conversion without using strings and Sorting\n\n## Intuition\n\nIn the previous approach, we converted every integer in `nums` to a string, mapped the changes, and converted it back to an integer. Can we directly convert the given integer to the mapped integer?\n\nObserve that to make changes to a specific digit, we must avoid altering the digits before and after it. This can be achieved by constructing the mapped integer one digit at a time. Start from the unit place, change the digit to its mapped value, and then move to the tenth place. After changing the digit at the tenth place, multiply it by 10 and add it to the unit place. Repeat this process for each position.\n\n## Algorithm\n\n1.  Initialize an array of pairs given by `storePairs`.\n2.  Iterate `i` through the `nums` array:\n    -   Initialize `mappedValue` with 0, `temp` with `nums[i]` and `place` with 1.\n    -   If `temp` is 0, push the value of `mapping[0]` in `storePairs`.\n    -   While `temp` is not equal to 0:\n        -   Increment `place * mapping[temp%10]` to `mappedValue`.\n        -   Multiply `place` by 10.\n        -   Divide `temp` by 10.\n    -   Push the value of `mappedValue` and the index in `storePairs`.\n3.  Sort the `storePairs` array.\n4.  Create an array `answer`.\n5.  Iterate through `storePairs` and append the `nums` value at the index to the `answer`.\n6.  Return the `answer` array.\n\n## Implementation\n\n\n```java []\npublic class Solution {\n\n    public int[] sortJumbled(int[] mapping, int[] nums) {\n        List<int[]> storePairs = new ArrayList<int[]>();\n\n        for (int i = 0; i < nums.length; i++) {\n            int mappedValue = 0;\n            int temp = nums[i];\n            int place = 1;\n\n            if (temp == 0) {\n                storePairs.add(new int[] { mapping[0], i });\n                continue;\n            }\n            while (temp != 0) {\n                mappedValue = place * mapping[temp % 10] + mappedValue;\n                place *= 10;\n                temp /= 10;\n            }\n            storePairs.add(new int[] { mappedValue, i });\n        }\n\n        Collections.sort(storePairs, (a, b) -> a[0] - b[0]);\n\n        int[] answer = new int[nums.length];\n        for (int i = 0; i < storePairs.size(); i++) {\n            answer[i] = nums[storePairs.get(i)[1]];\n        }\n\n        return answer;\n    }\n}\n```\n```python []\nclass Solution:\n    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:\n        store_pairs = []\n\n        for i in range(len(nums)):\n            mapped_value = 0\n            temp = nums[i]\n\n            # Start making changes from the units place.\n            place = 1\n            # If the value initially is 0, return mapping[0] and index.\n            if temp == 0:\n                store_pairs.append((mapping[0], i))\n                continue\n            # Repeat the process for units, tenths, hundredths.. places.\n            while temp != 0:\n                mapped_value = place * mapping[temp % 10] + mapped_value\n                place *= 10\n                temp //= 10\n            store_pairs.append((mapped_value, i))\n\n        # Sort the array in non-decreasing order by the first value (default).\n        store_pairs.sort()\n        answer = [nums[pair[1]] for pair in store_pairs]\n\n        return answer\n```\n```c++ []\nclass Solution {\npublic:\n    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {\n        vector<pair<int, int>> storePairs;\n\n        for (int i = 0; i < nums.size(); ++i) {\n            int mappedValue = 0;\n            int temp = nums[i];\n            // Start making changes from the units place.\n            int place = 1;\n            // If the value initially is 0, return mapping[0] and index.\n            if (temp == 0) {\n                storePairs.push_back({mapping[0], i});\n                continue;\n            }\n            // Repeat the process for units, tenths, hundredths.. places.\n            while (temp != 0) {\n                mappedValue = place * mapping[temp % 10] + mappedValue;\n                place *= 10;\n                temp /= 10;\n            }\n            storePairs.push_back({mappedValue, i});\n        }\n\n        // Sort the array in non-decreasing order by the first value (default).\n        sort(storePairs.begin(), storePairs.end());\n        vector<int> answer;\n        for (auto pair : storePairs) {\n            answer.push_back(nums[pair.second]);\n        }\n        return answer;\n    }\n};\n```\n\n## Complexity Analysis\n\nLet n be the size of the `nums` array.\n\n-   Time complexity:$$O(n\u22C5logn)$$\n    \n    For every integer in `nums`, we convert it to the mapped integer. The time taken for this operation is O(lengthofinteger) time, which is proportional to the logarithmic value of `n`. Therefore, the time complexity for these operations on `nums` is given by O(n\u22C5logn).\n    \n    Sorting the array of pairs takes O(n\u22C5logn) time. All other operations are linear or constant time.\n    \n    Therefore, the total time complexity is given by O(n\u22C5logn).\n    \n-   Space complexity: $$O(n)$$\n    \n    We create two new arrays of size `n`. Apart from this, some extra space is used when we sort arrays in place. The space complexity of the sorting algorithm depends on the programming language.\n    \n    -   In Python, the sort method sorts a list using the Timsort algorithm which is a combination of Merge Sort and Insertion Sort and has O(n) additional space.\n    -   In Java, `Arrays.sort()` is implemented using a variant of the Quick Sort algorithm which has a space complexity of O(logn) for sorting two arrays.\n    -   In C++, the `sort()` function is implemented as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worse-case space complexity of O(logn).\n    \n    Therefore, the total space complexity is given by O(n).\n\n\n# Code\n```\nclass Solution {\n    public int[] sortJumbled(int[] mapping, int[] nums) {\n        List<int[]> list=new ArrayList<>();\n        \n        for(int i=0;i<nums.length;i++){\n            int curr=nums[i];\n            int after=0;\n            int place=1;\n            if(curr==0){\n                list.add(new int[]{mapping[curr],i});\n                continue;\n            } \n            while(curr!=0){\n                after=place*mapping[curr%10]+after;\n                place*=10;\n                curr/=10;\n            }\n            list.add(new int[]{after,i});\n        }\n\n        Collections.sort(list, (a,b)->a[0]-b[0]);\n        int ans[]=new int[nums.length];\n        for(int i=0;i<nums.length;i++){\n            ans[i]=nums[list.get(i)[1]];\n        }\n        return ans;\n    }\n}\n```
['Array', 'Sorting', 'Python', 'C++', 'Java', 'Python3']