Easy Hash Table Sorting solution | Full Explaination
Intuition\nThe problem requires us to sort an array of integers based on their frequency of occurrence. If two numbers have the same frequency, they should be s
# Intuition\nThe problem requires us to sort an array of integers based on their frequency of occurrence. If two numbers have the same frequency, they should be sorted by their values in descending order.\n\n# To achieve this:\n\nCount Frequencies: First, we need to determine how often each number appears in the array.\nSort by Frequency and Value: Then, we need to sort the array such that elements with lower frequencies come first. For elements with the same frequency, sort them in descending order of their values.\n\n# Approach\n\n1. Frequency Counting:\n\n=> Use an unordered_map (hash map) to store the frequency of each integer in the array. This allows us to efficiently count the occurrences of each integer.\n\n=>Traverse the array once to populate the hash map, where the key is the integer and the value is its frequency.\n\n2. Custom Sorting:\n\n=> Use the std::sort function with a custom comparator to sort the array based on the frequencies stored in the hash map.\n=> The comparator function compares two elements, a and b:\nIf their frequencies are equal, sort by value in descending order.\nOtherwise, sort by frequency in ascending order.\n=> This ensures that elements with lower frequencies appear first, and among those with the same frequency, larger values come before smaller values.\n3. Return the Sorted Array:\n\n=> After sorting, return the array with elements ordered according to the specified criteria.\n\n# Complexity\n- Time complexity: O(nlogn)\n- Frequency Counting: The frequency count operation takesO(n) time, where n is the number of elements in the array.\n- Sorting: The sorting step takes O(nlogn) time. This is the dominant factor in the time complexity, as the sort operation is based on the comparison of elements.\n- Overall Time Complexity: The total time complexity is O(nlogn), dominated by the sorting step.\n\n- Space complexity: O(n)\n- Frequency Map: Storing the frequency of each number requires O(n) additional space, as we need to keep track of the frequency for each unique number in the array.\n- Sorting: The space used for sorting is O(1) if we consider the space required by the sorting algorithm itself.\n- Overall Space Complexity: The total space complexity is O(n), primarily due to the hash map used to store frequencies\n\n# Code\n```C++ []\n\nclass Solution {\npublic:\n    vector<int> frequencySort(std::vector<int>& nums) {\n        std::unordered_map<int, int> hmap;\n\n        for (int num : nums) {\n            hmap[num]++;\n        }\n\n        // Sort the nums vector with a custom comparator\n        sort(nums.begin(), nums.end(), [&](int a, int b) {\n            if (hmap[a] == hmap[b]) {\n                return a > b; // If frequencies are equal, sort by value in descending order\n            }\n            return hmap[a] < hmap[b]; // Otherwise, sort by frequency in ascending order\n        });\n\n        return nums;\n    }\n};\n```\n![Shinchan_upvote.jpg](https://assets.leetcode.com/users/images/a0636988-c2e9-4fbe-acb0-1be6639a2b6d_1721720731.3337893.jpeg)\n\n
['Array', 'Hash Table', 'Sorting', 'C++']