1636. Sort Array by Increasing Frequency - Explanation

Description

You are 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.

Constraints:

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

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Maps - Used to count the frequency of each element in the array
Custom Comparators - Sorting with multi-level criteria (primary by frequency, secondary by value)
Sorting Algorithms - Understanding how to apply custom sort keys or comparator functions

1. Custom Sort

Intuition

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).

Algorithm

Count the frequency of each number using a hash map.
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).
Return the sorted array.

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

public class Solution {
    public int[] frequencySort(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, (a, b) -> {
            int freqA = count.get(a), freqB = count.get(b);
            if (freqA != freqB) return Integer.compare(freqA, freqB);
            return Integer.compare(b, a);
        });

        return Arrays.stream(arr).mapToInt(i -> i).toArray();
    }
}

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;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number[]}
     */
    frequencySort(nums) {
        const count = {};
        for (let num of nums) {
            count[num] = (count[num] || 0) + 1;
        }

        nums.sort((a, b) => {
            if (count[a] !== count[b]) return count[a] - count[b];
            return b - a;
        });

        return nums;
    }
}

public class Solution {
    public int[] FrequencySort(int[] nums) {
        var count = new Dictionary<int, int>();
        foreach (int n in nums) {
            if (!count.ContainsKey(n)) count[n] = 0;
            count[n]++;
        }

        return nums.OrderBy(n => count[n]).ThenByDescending(n => n).ToArray();
    }
}

func frequencySort(nums []int) []int {
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }

    sort.Slice(nums, func(i, j int) bool {
        if count[nums[i]] != count[nums[j]] {
            return count[nums[i]] < count[nums[j]]
        }
        return nums[i] > nums[j]
    })

    return nums
}

class Solution {
    fun frequencySort(nums: IntArray): IntArray {
        val count = HashMap<Int, Int>()
        for (num in nums) {
            count[num] = count.getOrDefault(num, 0) + 1
        }

        return nums.sortedWith(compareBy({ count[it] }, { -it })).toIntArray()
    }
}

class Solution {
    func frequencySort(_ nums: [Int]) -> [Int] {
        var count = [Int: Int]()
        for num in nums {
            count[num, default: 0] += 1
        }

        return nums.sorted { a, b in
            if count[a]! != count[b]! {
                return count[a]! < count[b]!
            }
            return a > b
        }
    }
}

impl Solution {
    pub fn frequency_sort(nums: Vec<i32>) -> Vec<i32> {
        let mut count = HashMap::new();
        for &num in &nums {
            *count.entry(num).or_insert(0) += 1;
        }

        let mut nums = nums;
        nums.sort_by(|a, b| {
            let fa = count[a];
            let fb = count[b];
            if fa != fb {
                fa.cmp(&fb)
            } else {
                b.cmp(a)
            }
        });

        nums
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

Common Pitfalls

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.