1636. Sort Array by Increasing Frequency

Problem

Question

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

---

Solutions

1. Customized Sorting

Time Complexity: $O(n\log n)$ | Space Complexity: $O(n)$

The solution might be tricky in Python as we rarely sort elements based on two or more parameters. In the snippet below, you can see that we use (memo[x], -x) as the tuple-based key for sorting. In case the first parameter (memo[x]) is equal while comparing two elements, we refer to the second one (-x). For example, imagine:

• 2 occurs 5 times
• 3 occurs 5 times

The second argument (-x) guarantees that 3 will appear before 2 as -3 < -2.

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        #memo = defaultdict(int)
			
        #for num in nums:
        #    memo[num] += 1
        memo = Counter(nums)
        sorted_nums = sorted(nums, key=lambda x: (memo[x], -x))
        
        return sorted_nums

Or a very inefficientoneliner :

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

For comparison, here is Java and C++ implementations:

1. Java

Arrays.sort(numsObj, (a, b) -> {
    if (freq.get(a).equals(freq.get(b))) {
        return Integer.compare(b, a);
    }
    return Integer.compare(freq.get(a), freq.get(b));
});

2. C++

sort(nums.begin(), nums.end(), [&](int a, int b) {
    if (freq[a] == freq[b]) {
        return a > b; 
    }
    return freq[a] < freq[b];
});