LeetCode Entry

347. Top K Frequent Elements

22.05.2023 medium 2023 kotlin

First k unique elements sorted by frequency.

347. Top K Frequent Elements medium blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/220

Problem TLDR

First k unique elements sorted by frequency.

Intuition

Group by frequency 1 1 1 5 5 -> 1:3, 5:2, then bucket sort frequencies 2:5, 3:1, then flatten and take first k.

Approach

• We can use Kotlin collections api

  Complexity

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

Code

fun topKFrequent(nums: IntArray, k: Int): IntArray {
    val freq = nums.groupBy { it }.mapValues { it.value.size }
    val freqToNum = Array<MutableList<Int>>(nums.size + 1) { mutableListOf() }
    freq.forEach { (num, fr) -> freqToNum[nums.size + 1 - fr].add(num) }
    return freqToNum
        .filter { it.isNotEmpty() }
        .flatten()
        .take(k)
        .toIntArray()
}