LeetCode Entry

1636. Sort Array by Increasing Frequency

23.07.2024 easy 2024 kotlin rust

Sort by frequency or descending

1636. Sort Array by Increasing Frequency easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/679

Problem TLDR

Sort by frequency or descending #easy

Intuition

Sort with comparator. Another way is to do sorting two times but with a stable sort (in Kotlin it is by default, in Rust you must use sort instead of sort_unstable).

Approach

• pay attention: there are negative numbers
• Kotlin doesn’t have sortWith for IntArray

Complexity

• Time complexity: \(O(nlogn)\)

• Space complexity: \(O(n)\)

Code

    fun frequencySort(nums: IntArray): IntArray {
        val f = IntArray(202)
        for (n in nums) f[n + 100]++
        return nums
            .sortedWith(compareBy({ f[it + 100]}, { -it }))
            .toIntArray()
    }

    pub fn frequency_sort(mut nums: Vec<i32>) -> Vec<i32> {
        let mut f = vec![0; 201];
        for n in &nums { f[(n + 100) as usize] += 1 }
        nums.sort_unstable_by_key(|n| (f[(n + 100) as usize], -n));
        nums
    }