Sort Array by Increasing Frequency

Leetcode Problem:

• Sort Array by Increasing Frequency

Summary

• Given an array of integers, 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.

Approach

• The solution uses a frequency count array to store the frequency of each value, then sorts the array using a modified merge sort algorithm
• The modified merge sort algorithm uses a temporary array to store the merged elements and then copies them back to the original array.

Complexity

• O(n log n)

Explain

• The solution first creates a frequency count array `cnt` to store the frequency of each value
• Then it calls the `merge_sort` function to sort the array
• The `merge_sort` function recursively divides the array into two halves and sorts them separately
• Then it merges the two sorted halves using the `merge` function
• The `merge` function compares the frequencies of the values and sorts them in increasing order
• If multiple values have the same frequency, it sorts them in decreasing order
• Finally, the solution returns the sorted array.

Solution Code:

class Solution {
    int cnt[300] = {0};
    int tmp[100];
    void merge(vector& nums, int l, int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = i;
        while( i <= mid && j <= r){
            if (cnt[nums[i] + 100] < cnt[nums[j] + 100]){
                tmp[cur++] = nums[i++];
            } 
            else if(cnt[nums[i] + 100] == cnt[nums[j] + 100] && nums[i] > nums[j]){
                tmp[cur++] = nums[i++];
            }
            else{
                tmp[cur++] = nums[j++];
            }
        }
        while(i <= mid){
            tmp[cur++] = nums[i++];
        }
        for(i = l; i < cur; i++){
            nums[i] = tmp[i];
        }
    }
    void merge_sort(vector &nums, int l, int r){
        if (l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid+1, r);
        merge(nums, l, mid, r);
    }    
public:
    vector frequencySort(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            cnt[nums[i] + 100]++;
        }
        merge_sort(nums, 0, nums.size() -1);
        return nums;
    }
};