Solution: Sort Array by Increasing Frequency

Problem Statement

Given an array nums containing the integers, return the resultant array after sorting it in increasing order based on the frequency of the values. If two numbers have the same frequency, they should be sorted in descending numerical order.

Examples

Example 1:

Input: nums = [4, 4, 6, 2, 2, 2]
ExpectedOutput: [6, 4, 4, 2, 2, 2]
Justification: Here, '6' appears once, '4' appears twice, and '2' appears three times. Thus, numbers are first sorted by frequency and then by value when frequencies tie.

Example 2:

Input: nums =

.....

Like the course? Get enrolled and start learning!

Jimmy

· 2 years ago

In the solution, it implemented merge sort to sort by the frequency first and then by value (in descending order). Is there any reason why one can't implement a custom compare function which does the same thing? In an interview setting, it saves a lot more time and is less error prone.

In C++, I implemented something like this:

bool compare(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    if (a.first != b.first)
        return a.first < b.first;
    else
        return a.second > b.second;
}

Show 1 reply

Matteo Mortella

· a year ago

class Solution:
    # Method to sort the array based on frequency
    def frequencySort(self, nums):
        from collections import Counter

        freq = Counter(nums)

        buckets = [[] for _ in range(max(freq.values()))] # create k buckets

        for num in freq: # populate buckets (0-based)

            buckets[freq[num]-1].append(num) 

        sorted_arr = []

        for i in range(len(buckets)): # worst case: O(N*log(N))

            if len(buckets[i])>1: # more then one number with the same freq.

                buckets[i].sort(reverse=True)

                for j in range(len(buckets[i])):

                    tmp_list = []
                    tmp_list.append(buckets[i][j])

                    sorted_arr.extend(tmp_list*(i+1))

            else:

Dan Anderson

· 5 months ago

To match the solution, maybe the question should specify no use of built-ins?

Using built-ins in Python, the solution can be achieved in just a few lines:

from collections import Counter

class Solution:
    def frequencySort(self, nums):
        freq = Counter(nums)
        return sorted(nums, key=lambda x: (freq[x], -x))

And if we are to solve without using built-ins, bucket sort (roughly O(n) with k ~ n) seems like it would be a better fit than merge sort (O(n log n) average) as the range of potential frequencies is bounded by the size of the input array:

from collections import Counter

class Solution:
    def frequencySort(self, nums):
        freq = Counter(nums)

        buckets = [[] for _ in range(len(nums) + 1)]

        for num, f in freq.items():