1636.sort-array-by-increasing-frequency.md

1636. Sort Array by Increasing Frequency

Hash Table + Sorting

// Sort the map directly
fun frequencySort(nums: IntArray): IntArray {
    val countMap = HashMap<Int, Int>()
    for (num in nums) {
        countMap[num] = (countMap[num] ?: 0) + 1
    }
    val sortedMap =
        countMap
            .toList()
            .sortedWith(compareBy<Pair<Int, Int>> { (_, value) -> value }
                .thenByDescending { it.first })
            .toMap()
    val ans = IntArray(nums.size)
    var i = 0
    for ((k, v) in sortedMap) {
        repeat(v) {
            ans[i++] = k
        } 
    }
    return ans
}

// Using Java Collections API
fun frequencySort(nums: IntArray): IntArray {
    val countMap = HashMap<Int, Int>()
    for (num in nums) {
        countMap[num] = (countMap[num] ?: 0) + 1
    }
    val ans = MutableList(nums.size) { nums[it] }
    Collections.sort(ans) { n1, n2 ->
        val count1 = countMap[n1]!!
        val count2 = countMap[n2]!!
        if (count1 == count2) n2 - n1
        else count1 - count2
    }
    return ans.toIntArray()
}

// Using Kotlin APIs
fun frequencySort(nums: IntArray): IntArray {
    val countMap = HashMap<Int, Int>()
    for (num in nums) {
        countMap[num] = (countMap[num] ?: 0) + 1
    }

    val ans = nums.sortedWith(compareBy<Int> { countMap[it] }.thenByDescending { it })
    // Or equivalently
    // val ans = nums.sortedWith(compareBy({ countMap[it] }, {-it}))

    return ans.toIntArray()
}