1-liner|count freq[x+100] & sort by lambda vs Counting sort||0ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nSince the constraints -100 <= nums[i] <= 100 count freq[x+100] for x in nums\nThen sort
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince the constraints `-100 <= nums[i] <= 100` count freq[x+100] for x in nums\nThen sort it by a lambda which is fast both in C++& Python. Similar concept, using Counter in python, a 1-liner is given, the 1st version for that is slow but accepted; 1 of the reivised versions is presented.\n\nLater try other approach. 2nd approach is using counting sort which reduces the time complexity to $O(n+m)$.\n\nSimilar questions solved in LC:\n[451. Sort Characters By Frequency\n](https://leetcode.com/problems/sort-characters-by-frequency/solutions/4689181/just-arrays-3-kinds-of-sortings-no-hash-table-0ms-beats-100/)[2418. Sort the People\n](https://leetcode.com/problems/sort-the-people/solutions/5513898/sort-pairs-reuse-names-1-line-pack-heightsi-iinto-an-int17ms-beats-9705/)\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. count freq[x+100] for x in nums\n2. Sort nums w.r.t. the lambda function `[&](int x, int y){\n            return (freq[x+100]==freq[y+100])?x>y:freq[x+100]<freq[y+100];\n        }`\n3. 2nd approach uses counting sort which is harder than easy. On the other hand, its time is linear, but brings no benefit for the small sized testcases. The best record is 2ms.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n\\log n)$$\nCounting sort: $O(n+m)$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n $$O(m)$$ where m=max(nums)-min(nums)\n# Code||C++ 0ms beats 100%\n[submitted C++code](https://leetcode.com/problems/sort-array-by-increasing-frequency/submissions/1330076381/)\n```C++ []\nclass Solution {\npublic:\n    using int2=array<int,2>;\n    vector<int> frequencySort(vector<int>& nums) {\n        int n=nums.size(), freq[201]={0};\n        for(int x:nums){\n            freq[x+100]++;\n        }\n        \n        sort(nums.begin(), nums.end(), [&](int x, int y){\n            return (freq[x+100]==freq[y+100])?x>y:freq[x+100]<freq[y+100];\n        });\n        return nums;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n```Python []\nclass Solution:\n    def frequencySort(self, nums: List[int]) -> List[int]:\n        freq=[0]*201\n        for x in nums:\n            freq[x+100]-=1 \n        return sorted(nums, key=lambda x:(freq[x+100], x), reverse=True)\n        \n```\n# C++ using counting sort \n```\nclass Solution {\npublic:\n    // counting sort for unique x in the decreasing order \n    static void counting_sort(auto& arr) {// this simplifed version is sufficient for use\n        if (arr.empty()) return;\n        auto [xMin, xMax] = minmax_element(arr.begin(), arr.end());\n        int m = *xMin, v = *xMax - m + 1;\n        vector<bool> cnt(v, 0);\n        for (int x : arr)\n            cnt[x - m]=1;\n        for (int y = v-1, i=0; y >= 0; y--) { //sort in decreasing order\n            if (cnt[y]==0) continue;\n            arr[i]=y+m;\n            i++;\n        }\n    }\n\n    static vector<int> frequencySort(vector<int>& nums) {\n        const int n = nums.size();\n        vector<int> freq(201, 0);\n        int maxF = 0, maxX = -1;\n        for (int x : nums) {\n            x += 100; // x-min_x where min_x=-100\n            int f = ++freq[x];\n            maxX = max(x, maxX);\n            maxF = max(f, maxF);\n        }\n        vector<vector<int>> freqx(maxF + 1);\n        for (int x = 0; x <= maxX; x++) {\n            if (freq[x] > 0)\n                freqx[freq[x]].push_back(x-100); // Adjust value back\n        }\n\n        int i = 0;\n        for (int f = 1; f <= maxF; f++) {\n            auto& arr = freqx[f];\n            counting_sort(arr);\n            for (int x : arr) {// each x occurs f times\n                fill(nums.begin()+i, nums.begin()+i+f, x);\n                i+=f;\n            }\n        }\n        return nums;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# C++ using counting sort||simple version 0ms beats 100%\n```\nclass Solution {\npublic:\n    static vector<int> frequencySort(vector<int>& nums) {\n        const int n = nums.size();\n        vector<int> freq(201, 0);\n        int maxF = 0, maxX = -1;\n        for (int x : nums) {\n            x += 100; // x-min_x where min_x=-100\n            int f = ++freq[x];\n            maxX = max(x, maxX);\n            maxF = max(f, maxF);\n        }\n        vector<vector<int>> freqx(maxF + 1);\n        for (int x = maxX; x >=0; x--) {\n            if (freq[x] > 0)\n                freqx[freq[x]].push_back(x-100); // Adjust value back\n        }\n\n        int i = 0;\n        for (int f = 1; f <= maxF; f++) {\n            auto& arr = freqx[f];\n            for (int x : arr) {// each x occurs f times\n                fill(nums.begin()+i, nums.begin()+i+f, x);\n                i+=f;\n            }\n        }\n        return nums;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# revised Python 1-liner||Thanks to all who posted the comments & suggestions on this issue.\n```\nclass Solution:\n    def frequencySort(self, nums: List[int]) -> List[int]:\n        return sorted(nums, key=lambda x, K=Counter(nums):(K[x], -x))\n```
['Array', 'Hash Table', 'Sorting', 'Counting Sort', 'C++', 'Python3']