DMITRII’s Substack

Share this post

# 22.05.2023 [347. Top K Frequent Elements]

dmitriisamoilenko.substack.com

# 22.05.2023 [347. Top K Frequent Elements]

DMITRII SAMOILENKO
May 22, 2023
Share
Share this post

# 22.05.2023 [347. Top K Frequent Elements]

dmitriisamoilenko.substack.com

22.05.2023

347. Top K Frequent Elements medium
blog post

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()
}

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

Share
Share this post

# 22.05.2023 [347. Top K Frequent Elements]

dmitriisamoilenko.substack.com
Previous
Next
Comments
Top
New

No posts

Ready for more?

© 2023 DMITRII SAMOILENKO
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing