LeetCode 1636. Sort Array by Increasing Frequency

Description

https://leetcode.com/problems/sort-array-by-increasing-frequency/

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.

Return the sorted array.

Example 1:

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.

Example 2:

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

Example 3:

Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]

Constraints:

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

Explanation

Use a heap to store and output the elements by their frequency. Note that when using heapq.heappush(pq, (attribute1, attribute2), the heap compares the attribute1 first if two elements have the same attribute1, the heap compares attribute2. For this problem, we want to sort elements in decreasing order if multiple values have the same frequency. Therefore, when inserting the element, we use heapq.heappush(pq, (value, -key)) , where key is the element value.

Python Solution

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        counter = {}

        for num in nums:
            counter[num] = counter.get(num, 0) + 1
 
        pq = []
        for key, value in counter.items():
            heapq.heappush(pq, (value, -key))
        
        results = []
        for i in range(len(pq)):
            count, value = heapq.heappop(pq)
            for j in range(count):
                results.append(-value)
        
        return results