Sort Array by Increasing Frequency — LeetCode 1636 Python Solution

The problem

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

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.

Python solution

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

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1636. Sort Array by Increasing Frequency is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems