Sort array by increasing frequency

We will use a hashmap to store the frequency of each number. Then we will sort the array by the frequency of each number. If the frequency of two numbers is the same, we will sort them by the value of the number. Finally, we will return the sorted array.

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        counter = collections.Counter(nums)
        return sorted(nums, key=lambda x: (counter[x], -x))

Time complexity: O(nlog(n))
Space complexity: O(n)