Sort Numbers Using Custom Mapping - beats 100% - C
Intuition\nThe goal of this code is to sort an array of integers based on a custom mapping defined by another array. Each integer in the input array is transfor
# Intuition\nThe goal of this code is to sort an array of integers based on a custom mapping defined by another array. Each integer in the input array is transformed according to this mapping, and the transformed values are used for sorting. After sorting, the original order of integers is restored using the indices stored during transformation.\n# Approach\n**1.Conversion Function (convert):**\n- This function converts an integer into another integer based on a custom mapping provided as an array. For example, if mapping[3] = 7, then convert(3, mapping, size) would return 7.\n\n**2.Element Structure:**\n- Element structure is defined to store the original index and the transformed value of each number after applying the convert function.\n\n**3. Sorting Function (cmp):**\n- Comparator function cmp is used by qsort to sort an array of Element structures. It first compares based on the transformed values (val), and in case of ties, it uses the original indices (index) to maintain stability in sorting.\n\n**4. Sorting Process (sortJumbled):**\n- Initialize an array of Element structures (dup) where each element stores the original index and the transformed value of each number from the input array.\n- Sort the dup array using qsort based on the cmp function.\n- Create a result array where each element is assigned from the original array based on the sorted indices stored in the dup array.\n\n**5. Memory Management:**\n- Dynamically allocate memory for the result array (result) to be returned to the caller. The caller is responsible for freeing this memory.\n\n\n# Complexity\n## Time complexity:\n The most time-consuming operation is sorting the dup array using qsort, which has a time complexity of \uD835\uDC42(\uD835\uDC5B log \uD835\uDC5B), where n is the number of elements in the nums array. The conversion (convert) operation is \uD835\uDC42(\uD835\uDC51) where d is the number of digits in the largest number, but since d is relatively small compared to n, it doesn\'t dominate the complexity.\n\n## Space complexity:\nAdditional space complexity is primarily due to the dup array of Element structures, which requires \uD835\uDC42(\uD835\uDC5B) space. Sorting and other operations also contribute to space complexity, but they are dominated by the size of the dup array.\n\n\n# Code\n```\n/**\n * Note: The returned array must be malloced, assume caller calls free().\n */\n\ntypedef struct{\n    int index;\n    int val;\n} Element;\n\nint convert(int n, int* mapping, int size){\n    if(n==0){\n        return mapping[0];\n    }\n    int result =0;\n    int multiplier = 1;\n\n    while(n > 0){\n        int d = n % 10;\n        result = mapping[d] * multiplier + result;\n        multiplier *= 10;\n        n /= 10;\n    }\n\n    return result;\n}\n\nint cmp(const void* a, const void* b) {\n    Element* elemA = (Element*)a;\n    Element* elemB = (Element*)b;\n\n    if (elemA->val != elemB->val) {\n        return elemA->val - elemB->val;\n    } else {\n        return elemA->index - elemB->index;\n    }\n}\n\nint* sortJumbled(int* mapping, int mappingSize, int* nums, int numsSize, int* returnSize) {\n    *returnSize = numsSize;\n\n    Element dup[numsSize];\n    for(int i=0; i<numsSize; i++){\n        dup[i].index = i;\n        dup[i].val = convert(nums[i],mapping,mappingSize);\n    }\n\n    qsort(dup, numsSize, sizeof(Element), cmp);\n\n    int* result =(int*)malloc(numsSize*sizeof(int));\n    for(int i=0; i<numsSize; i++){\n        result[i] = nums[dup[i].index];\n    }\n    return result;\n}\n```
['C']