Sorting Technique🚀
Intuition\nThe problem asks us to sort an array of integers. A radix sort seems like a natural fit here since it sorts numbers by processing individual digits.A
# Intuition\nThe problem asks us to sort an array of integers. A radix sort seems like a natural fit here since it sorts numbers by processing individual digits.Also Radix sort can be used in the places like numbers which having more number of digits. This is an efficient sorting algorithm when the maximum number of digits is small compared to the size of the array.\n\n# Approach\nWe use Radix Sort to sort the numbers in the array. The key steps are:\n\n* First, we determine the maximum number of digits (in decimal) in the array.\n* Then, we sort the array one digit at a time from the least significant to the most significant, using counting sort for each digit position.\n* We store the frequency of each digit in the current position using a hash map and then accumulate those frequencies to determine the sorted positions.\n* Finally, we reconstruct the array based on the sorted positions for the current digit.\n\n# Complexity\n# Time complexity:\nTime complexity:\n\uD835\uDC42(\uD835\uDC5B.\uD835\uDC51)\nO(n\u22C5d) where n is the number of elements in the array and \uD835\uDC51 is the number of digits in the maximum number. Since \n\n# Space complexity:\n\uD835\uDC42(\uD835\uDC5B)\nO(n) because we use extra space for the counting arrays (frq and cumfrq) and the result array (ans)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> sortArray(vector<int>& nums) {\n        int bt = 0, val = INT_MIN,n = 0;\n\n        for (auto x : nums) {\n            ++n;\n            val = max(val,abs(x));\n        }\n\n        while (val!= 0) {\n            ++bt;\n            val /= 10;\n            // cout<<val<<" ";\n        }\n\n        for (int i=1; i<=bt; i++) {\n            unordered_map<int,int> frq,cumfrq;\n            vector<int> ans(n);\n            int t = pow(10,i);\n\n            for (int x : nums) {\n                int v = (x%t)/(t/10);\n                frq[v]++;\n            }\n\n            cumfrq[-9] = frq[-9];\n            for (int i=-8; i<=9;i++) {\n                cumfrq[i] = cumfrq[i-1] + frq[i];\n            }\n\n            for (int i=n-1;i>=0;i--) {\n                int g = cumfrq[(nums[i]%t) /(t/10)] - 1;\n                ans[g] = nums[i];\n                cumfrq[(nums[i]%t)/(t/10)]--;\n            }\n            nums = ans;\n        }\n\n        return nums;\n    }\n};\n```
['Sorting', 'Radix Sort', 'C++']