Just Counting | C++ In-Place Sorting 0 ms 100% | Python3 One-Liners 38 ms 98%
Intuition\nThe task is to sort the input array by the element frequencies, ascending. Two elements with the same frequencies should be arranged in descending or
# Intuition\nThe task is to sort the input array by the element frequencies, ascending. Two elements with the same frequencies should be arranged in descending order by their value. There could be up to $100$ elements in the range $[-100, 100]$.\n\n# Approach\n\n## C++\n\nFor fast enough languages we just introduce an array of frequency+value pairs. Since both count and value fit an 8-bit quantity, we allocate 16 bit for the pair, and the array size would be 201. The frequency would occupy a high-order byte, and the value would be in the low-order byte. To ensure proper comparison, we store frequencies as a complement to 100, so that 0 becomes 100, 1 becomes 99, etc., and the max possible frequency of 100 becomes 0. The value part is biased by 100, so that -100 becomes 0, -99 becomes 1, etc., and 100 becomes 200. This ensures the proper comparison ordering.\n\nWhen initializing the frequencies, we put 100 in the high-order byte, and the array index (0..200) in the low-order byte. This is easily achievable with `iota` in C++.\n\nThen we run through the array elements and for each element we subtract 1 from the frequency byte, i.e. we subtract 256 from the array element.\n\nThen we sort the array in descending order, which ensures that it\'s ascending by frequency and descending by value, and frequency comes first in comparisons. It\'s small enough to use a conventional STL sort (though it\'s still possible to apply a count sorting to it).\n\nFinally, we unfold the counters to the input array to reuse its storage. Each value (low-order byte) is added its frequency times (high order byte complemented to 100 again).\n\n## Java\n\nA Java solution is similar to a C++ one with the exception that we store frequencies as is and complement values. The point is that `Arrays.sort` can only sort ascending, and boxing and comparators would kill performance. Since there are no on-stack allocation of arrays in Java, we also use a static link to the frequencies array, allocated once and for all.\n\n## Python\n\nFor Python it\'s somewhat a different story. When programming in Python we should stick to libraries (written mostly in C) and use the minimum of Python code and data.\n\nThe counting could be achieved by accumulating values in `statistics.Counter` which is essentially a dictionary with values as keys and their frequencies as values.\n\nThe `Counter` can return accumulated statistics as key-value pairs, either sorted by counter descending (using `most_common`) or in a random order like `dict` does (using `items`). Elements with same frequencies would be returned by `most_common` in their order of appearence in the input data, which is not what we want. We have to apply our own ordering, therefore we use `Counter.items` method to avoid extra sorting overhead.\n\nOnce we have a sequence of pairs, we could sort it by count ascending and value descending, passing an appopriate sort key to the method.\n\nAnd finally we need to unfold the `Counter` to an array as per task requirements. We use two approaches here: `sum` of lists and chaining of iterators, just to compare their execution statistics. `sum` and list multiplication are builtin capabilities of the language, and `repeat` and `chain` are available in the `itertools` library.\n\nWhen we use `sum` to concatenate the lists, we have to materialize a list for each value, then a list for value its count times, a list of lists and a list for each intermediate concatenation (so if we have e.g. lists a, b, c, d, then intermediate lists are created for `a`, `b`, `c`, `d`, their multiples by count, then a list of lists (containing all multiples), then `a + b`, `a + b + c` and a final one for `a + b + c + d`).\n\nThe itertools stuff has an advantage that it operates iterators. `repeat` creates an iterator to return the given value the given number of times, and `chain` flattens the iterator of iterators to an iterator of values. Technically we would need to wrap the chain in a `list` afterwards, but the function happens to pass tests without that.\n\n# Complexity\n- Time complexity: $O(n \\times r \\times log(r))$\n\n- Space complexity: $O(r)$ ($O(n + r)$ for Python)\n\n(where $n$ is the input array size, and $r$ is the range of values (i.e. $201$))\n\n# Code\n``` C++ []\nclass Solution {\npublic:\n    static vector<int> frequencySort(vector<int>& nums) {\n        constexpr int8_t MINV = -100, MAXV = 100;\n        constexpr uint8_t FSIZE = MAXV - MINV + 1u;\n        uint16_t freqsv[FSIZE];\n        iota(freqsv, freqsv + FSIZE, 100u << 8);\n        for (const int v : nums)\n            freqsv[v-MINV] -= 1u << 8;\n        sort(freqsv, freqsv + FSIZE, greater());\n        nums.clear();\n        for (const uint16_t fv : freqsv)\n            nums.insert(nums.end(), 100u - (fv >> 8), (fv & 0xFF) + MINV);\n        return move(nums);\n    }\n};\n```\n``` Java []\nclass Solution {\n    private static final byte MINV = -100, MAXV = 100;\n    private static final short FSIZE = MAXV - MINV + 1;\n    private static final short[] freqsv = new short[FSIZE];\n    \n    public static int[] frequencySort(final int[] nums) {\n        for (int i = 0; i < FSIZE; i++)\n            freqsv[i] = (short)(FSIZE - i);\n        for (final int v : nums)\n            freqsv[v-MINV] += 1 << 8;\n        Arrays.sort(freqsv);\n        int i = 0;\n        final int VCOMP = FSIZE - MAXV;\n        for (final short fv : freqsv)\n            Arrays.fill(nums, i, i += (fv >> 8), VCOMP - (fv & 0xFF));\n        return nums;\n    }\n}\n```\n``` Python3/sum []\nclass Solution:\n    def frequencySort(self, nums: List[int]) -> List[int]:\n        return sum([[n] * c for n, c in sorted(Counter(nums).items(), key=lambda p: (p[1], -p[0]))], [])\n```\n``` Python3/chain []\nclass Solution:\n    def frequencySort(self, nums: List[int]) -> List[int]:\n        return chain.from_iterable(repeat(n, c) for n, c in sorted(Counter(nums).items(), key=lambda p: (p[1], -p[0])))\n```\n\n# Measurements\n\n|Language|Time,ms|Beating|Memory,Mb|Beating|Submission Link|\n|-|-|-|-|-|-|\n| C++ | 0 | 100% | 14.92 | 37.05% | https://leetcode.com/problems/sort-array-by-increasing-frequency/submissions/1330318847 |\n| Java | 3 | 97.80% | 43.42 | 98.20% | https://leetcode.com/problems/sort-array-by-increasing-frequency/submissions/1330520862 |\n| Python3/sum | 54 | 30.03% | 16.71 | 12.04% | https://leetcode.com/problems/sort-array-by-increasing-frequency/submissions/1330380423 |\n| Python3/chain | 38 | 98.24% | 16.76 | 12.04% | https://leetcode.com/problems/sort-array-by-increasing-frequency/submissions/1330427477 |\n\nNote that the chaining approach in Python is noticeably faster even with such tiny amount of data.\n
['Array', 'Bit Manipulation', 'Sorting', 'Counting', 'C++', 'Java', 'Python3']