Sorting Elements of an Array by Frequency

Given an array of integers arr, sort the array according to the frequency of elements, i.e. elements that have higher frequency comes first. If the frequencies of two elements are the same, then the smaller number comes first.

Examples :

Input: arr[] = [5, 5, 4, 6, 4]
Output: [4, 4, 5, 5, 6]
Explanation: The highest frequency here is 2. Both 5 and 4 have that frequency. Now since the frequencies are the same the smaller element comes first. So 4 4 comes first then comes 5 5. Finally comes 6. The output is 4 4 5 5 6.

Input: arr[] = [9, 9, 9, 2, 5]
Output: [9, 9, 9, 2, 5]
Explanation: The highest frequency here is 3. Element 9 has the highest frequency So 9 9 9 comes first. Now both 2 and 5 have the same frequency. So we print smaller elements first. The output is 9 9 9 2 5.

Expected Time Complexity: O(n*logn)
Expected Space Complexity: O(n)

Constraints:
1 ≤ arr.size() ≤ 10⁵
1 ≤ arr[i]≤ 10⁵

Approach 01:

class Solution {
  public:
    vector<int> sortByFreq(vector<int>& nums) {
        unordered_map<int, int> count;
        vector<pair<int, int>> frequency_pairs;
        
        // Count the frequency of each number
        for (int num : nums) {
            count[num]++;
        }

        // Create a list of pairs (frequency, number)
        for (auto& it : count) {
            frequency_pairs.push_back({it.second, it.first});
        }

        // Sort by frequency in ascending order, then by value in descending order
        sort(frequency_pairs.begin(), frequency_pairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            if (a.first == b.first)
                return a.second < b.second; // Sort by value in descending order
            return a.first > b.first; // Sort by frequency in ascending order
        });

        vector<int> result;
        for (auto& p : frequency_pairs) {
            result.insert(result.end(), p.first, p.second);
        }

        return result;
        
    }
};

import collections
class Solution:
    def sortByFreq(self,nums):
        count = collections.Counter(nums)
        # Create a list of tuples (frequency, number)
        frequency_pairs = [(freq, num) for num, freq in count.items()]
        
        # Sort by frequency in ascending order, then by value in descending order
        frequency_pairs.sort(key=lambda x: (x[0], -x[1]))
        
        result = []
        for freq, num in frequency_pairs:
            result.extend([num] * freq)
        
        return result[::-1]

Time Complexity

• Frequency Counting:

  Counting the frequency of each number takes \( O(\text{n}) \) time, where \( \text{n} \) is the number of elements in the input vector nums.

• Building Frequency Pairs:

  Creating a list of frequency pairs takes \( O(\text{k}) \) time, where \( \text{k} \) is the number of unique elements in nums.

• Sorting Frequency Pairs:

  Sorting the frequency pairs takes \( O(\text{k} \log \text{k}) \) time, due to the sorting algorithm used on the list of frequency pairs.

• Constructing the Result:

  Constructing the final sorted list takes \( O(\text{n}) \) time, as each element is inserted back into the result vector based on its frequency.

• Overall Time Complexity:

  The overall time complexity is \( O(\text{n} + \text{k} \log \text{k}) \), where \( \text{n} \) is the total number of elements in nums and \( \text{k} \) is the number of unique elements.

Space Complexity

• Frequency Map:

  The frequency map requires \( O(\text{k}) \) space, where \( \text{k} \) is the number of unique elements in nums.

• Frequency Pairs:

  The frequency pairs vector requires \( O(\text{k}) \) space to store the pairs of (frequency, number).

• Result Vector:

  The result vector requires \( O(\text{n}) \) space to store the sorted elements.

• Overall Space Complexity:

  The overall space complexity is \( O(\text{n} + \text{k}) \), dominated by the result vector and frequency pairs.