Sort Array by Increasing Frequency

How it works

We need to sort elements by how often they appear, with less frequent elements coming first. When two elements have the same frequency, the larger one should come first. A custom comparator lets us define this two-level sorting logic: primary sort by frequency (ascending), secondary sort by value (descending).

Steps

1. Count the frequency of each number using a hash map.
2. Sort the array using a custom comparator that:
   • Compares by frequency first (lower frequency comes first).
   • If frequencies are equal, compares by value (larger value comes first).
3. Return the sorted array.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Reversing the Tiebreaker Logic

The problem requires that when frequencies are equal, larger values should come first (descending order by value). A common mistake is sorting by ascending value instead, which produces incorrect output for elements with the same frequency.

Sorting by Frequency in Descending Order

The problem asks for increasing frequency order (less frequent elements first). Accidentally sorting by descending frequency places the most frequent elements first, which is the opposite of what is required.

from typing import List
from collections import Counter

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        count = Counter(nums)
        nums.sort(key=lambda n: (count[n], -n))
        return nums

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }

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

        return nums;
    }
};