Solution For Sort Array By Increasing Frequency

The problem “Sort Array By Increasing Frequency” on Leetcode is as follows:

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.

Example 1:

Input: nums = [1,1,2,2,2,3] Output: [3,1,1,2,2,2] Explanation: ‘3’ has a frequency of 1, ‘1’ has a frequency of 2, and ‘2’ has a frequency of 3.
Example 2:

Input: nums = [2,3,1,3,2] Output: [1,2,2,3,3] Explanation: ‘1’ has a frequency of 1, ‘2’ has a frequency of 2, and ‘3’ has a frequency of 2.

To solve this problem, we need to count the frequency of each element in the array and then sort the array based on the frequency. We can accomplish this by using a hashmap to count the frequency. Then, we can create a custom comparator function that compares the frequency of two elements and sorts them accordingly.

The solution to the problem can be broken down into the following steps:

1. Create a hashmap to count the frequency of each element in the array.
2. Create a custom comparator function that sorts two elements based on their frequency and value.
3. Sort the array using the custom comparator created in step 2.

Here’s the code to solve the problem:

“`
class Solution {
public int[] frequencySort(int[] nums) {
Map freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}

Arrays.sort(nums, new Comparator<Integer>() {
  public int compare(Integer a, Integer b) {
    if (freq.get(a) != freq.get(b)) {
      return freq.get(a) - freq.get(b);
    } else {
      return b - a;
    }
  }
});

return nums;

}
}
“`

Time Complexity: O(NlogN), where N is the length of the array.
Space Complexity: O(N), where N is the length of the array.

Step by Step Implementation For Sort Array By Increasing Frequency

import java.util.*; 
  
class Solution 
{ 
    static int[] sortByFreq(int a[], int n) 
    { 
        HashMap hm = new HashMap<>(); 
       
        for (int i = 0; i < n; i++) 
            hm.put(a[i], hm.getOrDefault(a[i], 0) + 1); 
       
        PriorityQueue pq = new PriorityQueue<>(new Comparator() 
        { 
            @Override
            public int compare(Pair p1, Pair p2) 
            { 
                if (p1.freq == p2.freq) 
                    return p1.value - p2.value; 
       
                return p2.freq - p1.freq; 
            } 
        }); 
       
        for (Map.Entry entry : hm.entrySet()) 
            pq.add(new Pair(entry.getKey(), entry.getValue())); 
       
        int index = 0; 
        while (!pq.isEmpty()) 
        { 
            Pair p = pq.poll(); 
           
            for (int i = 0; i < p.freq; i++) 
                a[index++] = p.value; 
        } 
       
        return a; 
    } 
}

def frequencySort(nums):
    
    # create a dictionary to store the frequencies of each element
    freq = {}
    for i in nums:
        if i in freq:
            freq[i] += 1
        else:
            freq[i] = 1
    
    # sort the dictionary by values in increasing order
    sorted_freq = sorted(freq.items(), key=lambda kv: kv[1])
    
    # create a new list consisting of the elements in sorted order
    res = []
    for i in sorted_freq:
        for j in range(i[1]):
            res.append(i[0])
    
    return res

var frequencySort = function(nums) {
    // create an empty map
    let map = {};
    
    // fill the map with the number of occurrences of each number
    for (let i = 0; i < nums.length; i++) {
        if (map[nums[i]]) {
            map[nums[i]]++;
        } else {
            map[nums[i]] = 1;
        }
    }
    
    // sort the map in increasing order of frequency
    let sortedMap = Object.keys(map).sort((a, b) => map[a] - map[b]);
    
    // fill the output array with the numbers in sorted order
    let output = [];
    for (let i = 0; i < sortedMap.length; i++) {
        for (let j = 0; j < map[sortedMap[i]]; j++) {
            output.push(sortedMap[i]);
        }
    }
    
    return output;
};

vector frequencySort(vector& nums) {
        // Create a map of numbers to their frequencies
        unordered_map freq;
        for (int n : nums) {
            freq[n]++;
        }
        
        // Sort the numbers by their frequencies
        sort(nums.begin(), nums.end(), [&](int a, int b) {
            return freq[a] < freq[b] || (freq[a] == freq[b] && a > b);
        });
        
        return nums;
    }

public int[] FrequencySort(int[] nums) { // Create a dictionary to store the number of times each number appears in the array Dictionary numFrequency = new Dictionary(); foreach(int num in nums) { if(numFrequency.ContainsKey(num)) { numFrequency[num]++; } else { numFrequency.Add(num, 1); } } // Sort the dictionary by the values (frequency) in descending order var sortedDict = from entry in numFrequency orderby entry.Value descending select entry; // Create and return an array of the numbers in the dictionary, sorted by frequency return sortedDict.Select(x => x.Key).ToArray(); }