2191. MOST DETAILED EXPLANATION | MUST READ FOR UNDERSTANDING | STEP BY STEP
Intuition\nThe problem requires sorting an array of integers (nums) based on a custom digit-to-digit mapping (mapping). Each digit in the numbers of nums is tra
# Intuition\nThe problem requires sorting an array of integers (`nums`) based on a custom digit-to-digit mapping (`mapping`). Each digit in the numbers of `nums` is transformed according to the `mapping` array. We then need to sort the numbers in `nums` based on these transformed numbers.\n\nThe key steps are:\n1. Transform each number in `nums` using the given `mapping`.\n2. Pair each transformed number with its original number.\n3. Sort these pairs based on the transformed numbers.\n4. Extract and return the original numbers in the order determined by the sorted transformed numbers.\n\n\n# Approach\n1. **Initialization**:\n   - Create an array `result` to store the final sorted numbers.\n   - Create a 2D array `map` to store pairs of transformed numbers and their corresponding original numbers.\n\n2. **Transform Numbers**:\n   - Iterate through each number in `nums`.\n   - For each number:\n     - If the number is `0`, directly map it using `mapping[0]`.\n     - Otherwise, decompose the number into its digits, map each digit using `mapping`, and reconstruct the transformed number.\n   - Store the transformed number and the original number as a pair in the `map` array.\n\n3. **Sort Pairs**:\n   - Sort the `map` array based on the transformed numbers (first element of each pair).\n\n4. **Extract Sorted Numbers**:\n   - Iterate through the sorted `map` array.\n   - Extract the original numbers (second element of each pair) and store them in `result`.\n\n5. **Return Result**:\n   - Return the `result` array which contains the original numbers sorted based on the transformed numbers.\n\n# Dry Run Explanation\n\n## Initial Setup\nLet\'s assume the following input:\n- `mapping = [3, 5, 4, 7, 2, 8, 9, 0, 6, 1]`\n- `nums = [990, 332, 981]`\n\nHere is the initial state of variables:\n- `len = nums.length = 3`\n- `result = new int[len] = [0, 0, 0]`\n- `map = new int[len][2] = [[0, 0], [0, 0], [0, 0]]`\n\n## Step-by-Step Execution\n\n### First Iteration (i = 0)\n- `temp = nums[0] = 990`\n\n**Mapping `990`**:\n- `tempSum = 0`\n- `power = 0`\n- `temp % 10 = 0` \u2192 `mapping[0] = 3`\n  - `tempSum += 3 * 10^0 = 3`\n  - `temp = 99`\n  - `power = 1`\n- `temp % 10 = 9` \u2192 `mapping[9] = 1`\n  - `tempSum += 1 * 10^1 = 10`\n  - `tempSum = 13`\n  - `temp = 9`\n  - `power = 2`\n- `temp % 10 = 9` \u2192 `mapping[9] = 1`\n  - `tempSum += 1 * 10^2 = 100`\n  - `tempSum = 113`\n  - `temp = 0`\n  - `power = 3`\n\n**Updating `map`**:\n- `map[0][0] = 113`\n- `map[0][1] = 990`\n- `map = [[113, 990], [0, 0], [0, 0]]`\n\n### Second Iteration (i = 1)\n- `temp = nums[1] = 332`\n\n**Mapping `332`**:\n- `tempSum = 0`\n- `power = 0`\n- `temp % 10 = 2` \u2192 `mapping[2] = 4`\n  - `tempSum += 4 * 10^0 = 4`\n  - `temp = 33`\n  - `power = 1`\n- `temp % 10 = 3` \u2192 `mapping[3] = 7`\n  - `tempSum += 7 * 10^1 = 70`\n  - `tempSum = 74`\n  - `temp = 3`\n  - `power = 2`\n- `temp % 10 = 3` \u2192 `mapping[3] = 7`\n  - `tempSum += 7 * 10^2 = 700`\n  - `tempSum = 774`\n  - `temp = 0`\n  - `power = 3`\n\n**Updating `map`**:\n- `map[1][0] = 774`\n- `map[1][1] = 332`\n- `map = [[113, 990], [774, 332], [0, 0]]`\n\n### Third Iteration (i = 2)\n- `temp = nums[2] = 981`\n\n**Mapping `981`**:\n- `tempSum = 0`\n- `power = 0`\n- `temp % 10 = 1` \u2192 `mapping[1] = 5`\n  - `tempSum += 5 * 10^0 = 5`\n  - `temp = 98`\n  - `power = 1`\n- `temp % 10 = 8` \u2192 `mapping[8] = 6`\n  - `tempSum += 6 * 10^1 = 60`\n  - `tempSum = 65`\n  - `temp = 9`\n  - `power = 2`\n- `temp % 10 = 9` \u2192 `mapping[9] = 1`\n  - `tempSum += 1 * 10^2 = 100`\n  - `tempSum = 165`\n  - `temp = 0`\n  - `power = 3`\n\n**Updating `map`**:\n- `map[2][0] = 165`\n- `map[2][1] = 981`\n- `map = [[113, 990], [774, 332], [165, 981]]`\n\n## Sorting the Map\nWe sort `map` based on the first column (mapped values):\n- Before sorting: `map = [[113, 990], [774, 332], [165, 981]]`\n- After sorting: `map = [[113, 990], [165, 981], [774, 332]]`\n\n## Constructing Result Array\nWe extract the original numbers in the order of sorted mapped values:\n- `result[0] = map[0][1] = 990`\n- `result[1] = map[1][1] = 981`\n- `result[2] = map[2][1] = 332`\n\nFinal `result = [990, 981, 332]`\n\n## Conclusion\nThe final sorted array based on the jumbled mapping is `[990, 981, 332]`.\n\n# Complexity\n- Time complexity:\n $$O(nlog(n))$$ \n\n- Space complexity:\n $$O(n)$$ \n\n# Code\n```\nclass Solution {\n    public int[] sortJumbled(int[] mapping, int[] nums) {\n\n        int len = nums.length ;\n\n        int[] result = new int[len] ;\n        int[][] map = new int[len][2] ;\n\n        for(int i=0;i<len;i++)\n        {\n            int temp = nums[i] ;\n\n            if(temp == 0)\n            {\n                map[i][0] = mapping[0] ;\n                map[i][1] = 0 ;\n            }\n            else\n            {\n                int tempSum = 0 ;\n                int power = 0 ;\n\n                while(temp > 0)\n                {\n                    tempSum += mapping[temp%10]*Math.pow(10,power) ;\n                    temp = (temp - temp%10)/10 ;\n                    power++ ;\n                }\n\n                map[i][0] = tempSum ;\n                map[i][1] = nums[i] ;\n            }\n        }\n\n        Arrays.sort(map, new Comparator<int[]>() {\n            @Override\n            public int compare(int[] a, int[] b) {\n                return Integer.compare(a[0], b[0]);\n            }\n        });\n\n        for(int i=0;i<len;i++)\n        {\n            result[i] = map[i][1] ;\n        }\n\n        return result ;\n    }\n}\n```\n![image.png](https://assets.leetcode.com/users/images/e03a118d-d072-460b-b743-c948a395e85d_1721811214.9779344.png)\n\n![Screenshot from 2024-07-09 09-56-34.png](https://assets.leetcode.com/users/images/4cc3afbd-23d8-46eb-9bf5-6db81317fb44_1721811282.8999882.png)\n\n
['Java']