✅💯🔥Explanations No One Will Give You🎓🧠Very Detailed Approach🎯🔥Extremely Simple And Effective🔥
\n        \n            \n                Never limit yourself because of others\u2019 limited imagination; never limit others because of your own limited imagi
<blockquote>\n        <p>\n            <b>\n                Never limit yourself because of others\u2019 limited imagination; never limit others because of your own limited imagination\n            </b>        \n        </p>\n        <p>\n            --- Mae Jemison ---\n        </p>\n</blockquote>\n\n# \uD83D\uDC51Problem Explanation and Understanding:\n\n## \uD83C\uDFAF Problem Description\nYou are given an integer array `nums` and asked to sort this array by frequency of its elements first (In increasing order) and by elements theyselves second (In decreasing order).\n\n## \uD83D\uDCE5\u2935\uFE0F Input:\n- Integer array `nums`\n\n## \uD83D\uDCE4\u2934\uFE0F Output:\nArray after perfoming sorting\n\n---\n\n# 1\uFE0F\u20E3\uD83D\uDE0E Approach: Custom Sort Comparator\n\n# \uD83E\uDD14 Intuition\n- We know how to perform sorting with comparators but we need to somehow optimize getting frequency, because counting number of elements iterating through whole list for every element is quite unefficient.\n- One of your choices - hashmap, but since constraints are pretty small I would say that using array with constant space (for this problem) can help to achieve O(1) space with counting sort but since there functions for sorting (like in Python) which uses algorithms like Timsort for sorting they use extra space in their implementation O(n) \n- Using frequency counter and elements themselves we can easily sort array by creating new custom comparator and pass it to the sort function.\n- Because we can have negative values (-100 <= num <= 100) in order to find index for counter for current element we must add to this element 100 - think about it, for -100 index will be 0, for -99 index will be 1 and for 100 index will be 200 (So we need 201 elements in the array - 100 + 100 + 1 (100 negative + 100 positive + zero))\n\n# \uD83D\uDC69\uD83C\uDFFB\u200D\uD83D\uDCBB Coding \n- Initializes a list `count` of size 201 with all elements set to 0.\n- Iterates over each number `num` in `nums`.\n- Increments the count of `num + 100` in the `count` list.\n- Sorts `nums` using a custom key.\n- The custom key sorts `nums` based on two criteria: the frequency of each number (increasing order) and the value of the number itself (decreasing order if frequencies are the same).\n- Returns the sorted `nums` list.\n\n# \uD83D\uDCD7 Complexity Analysis\n- \u23F0 Time complexity: O(n * log n), since we use built-in sort functions which is n * log n for most languages\n- \uD83E\uDDFA Space complexity: O(n), since since most sort functions use extraspace up to O(n) but if we don\'t count this our implementation takes O(1) space (array always have a size of 201)\n\n# \uD83D\uDCBB Code\n``` python []\nclass Solution:\n    def frequencySort(self, nums: list[int]) -> list[int]:\n        count: list[int] = [0 for _ in range(201)]\n        for num in nums:\n            count[num + 100] += 1\n        nums.sort(key=lambda val: (count[val + 100], -val))\n        return nums\n```\n``` C++ []\nclass Solution {\npublic:\n    vector<int> frequencySort(vector<int>& nums) {\n        vector<int> count(201, 0);\n        for (int num : nums) {\n            count[num + 100]++;\n        }\n        sort(nums.begin(), nums.end(), [&](int a, int b) {\n            if (count[a + 100] == count[b + 100])\n                return a > b;\n            return count[a + 100] < count[b + 100];\n        });\n        return nums;\n    }\n};\n```\n``` JavaScript []\nfunction frequencySort(nums) {\n    let count = Array(201).fill(0);\n    nums.forEach(num => {\n        count[num + 100]++;\n    });\n    return nums.sort((a, b) => {\n        if (count[a + 100] === count[b + 100]) {\n            return b - a;\n        }\n        return count[a + 100] - count[b + 100];\n    });\n}\n```\n``` Java []\nclass Solution {\n    public int[] frequencySort(int[] nums) {\n        int[] count = new int[201];\n        for (int num : nums) {\n            count[num + 100]++;\n        }\n        Integer[] numsArr = Arrays.stream(nums).boxed().toArray(Integer[]::new);\n        Arrays.sort(numsArr, (a, b) -> {\n            if (count[a + 100] == count[b + 100]) {\n                return b - a;\n            }\n            return count[a + 100] - count[b + 100];\n        });\n        return Arrays.stream(numsArr).mapToInt(Integer::intValue).toArray();\n    }\n}\n```\n``` C []\nint compare(const void* a, const void* b, void* count) {\n    int valA = *(int*)a;\n    int valB = *(int*)b;\n    int* cnt = (int*)count;\n\n    if (cnt[valA + 100] == cnt[valB + 100]) {\n        return valB - valA;\n    }\n    return cnt[valA + 100] - cnt[valB + 100]; \n}\n\nint* frequencySort(int* nums, int numsSize, int* returnSize) {\n    int count[201] = {0};\n    for (int i = 0; i < numsSize; i++) {\n        count[nums[i] + 100]++;\n    }\n\n    qsort_r(nums, numsSize, sizeof(int), compare, count);\n\n    *returnSize = numsSize;\n    return nums;\n}\n```\n\n# Additional Python One-liner (Not recommend to use, it\'s slow because, I think, it creates new Counter() object for every iteration (element) and also creates new array in memory instead of using input)\n```python\nclass Solution:\n    def frequencySort(self, nums: list[int]) -> list[int]:\n        return sorted(nums, key=lambda val: (Counter(nums)[val], -val))\n```\n\n## \uD83D\uDCA1\uD83D\uDCA1\uD83D\uDCA1I encourage you to check out [my profile](https://leetcode.com/heir-of-god/) and [Project-S](https://github.com/Heir-of-God/Project-S) project for detailed explanations and code for different problems (not only Leetcode). Happy coding and learning!\uD83D\uDCDA\n\n### Sorry for that, but I missed the moment repository gets 25 stars\u2B50 I want to say much thanks for everyone who support me this way, you all are great, I really appreciate that, keep moving!\n\n<div align="center">\n\n![image.png](https://assets.leetcode.com/users/images/b64095d8-3f2a-49f3-93ec-c9a8c9992acf_1721708995.7374904.png)\n\n</div>\n\n### Please consider *upvote*\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F because I try really hard not just to put here my code and rewrite testcase to show that it works but explain you WHY it works and HOW. Thank you\u2764\uFE0F\n\n## If you have any doubts or questions feel free to ask them in comments. I will be glad to help you with understanding\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\n\n![There is image for upvote](https://assets.leetcode.com/users/images/fde74702-a4f6-4b9f-95f2-65fa9aa79c48_1716995431.3239644.png)\n
['Array', 'Hash Table', 'C', 'Sorting', 'Counting Sort', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']