Sort Array by Increasing Frequency

You can solve this problem by first counting the frequency of each number using a dictionary, and then using Python’s built-in sorting function sorted() with a custom sorting key.

The custom sorting key is a function that takes an element of the list (in this case, a number from nums) and returns a value that sorted() uses to sort the elements. In this case, we want to sort by frequency first (in ascending order), and then by the number itself (in descending order).

from collections import Counter

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        # count the frequency of each number
        freq = Counter(nums)

        # sort by frequency (ascending) and value (descending)
        return sorted(nums, key=lambda x: (freq[x], -x))

Let’s break down how the key function works:

  • freq[x] is the frequency of the number x. This is the primary sort key, and because we want to sort by frequency in ascending order, we don’t need to do anything special here.

  • -x is the negation of the number x. This is the secondary sort key, and it is used when the frequencies are the same. Because we want to sort by number in descending order, we negate the numbers to reverse the order of the sort. Python’s sorted() function sorts in ascending order by default, but by negating the numbers, we make it sort in descending order instead.