Solving 'top k frequent elements' using bucket sort

tl;dr: an efficient approach to finding the k most frequent elements in an array

📝 Problem Statement

The problem Top K Frequent Elements requires us to return the k most frequent elements from an array of integers.

💡 My Initial Thought Process

At first, I thought of using a HashMap to count the frequency of each element, and then iterating through all keys to find the top k elements.
But then I hit a roadblock:

How do I efficiently find the top k frequent elements?
If I just iterate through the map k times, I end up with an O(N²) solution in the worst case.
Sorting all elements by frequency would take O(N log N), which feels unnecessary when I only need the top k.

This forced me to rethink the problem.

🤯 My Intuition & “Aha!” Moment

Instead of focusing on sorting elements, I started thinking:

“What if I group numbers by how frequently they appear?"
"Since the maximum frequency an element can have is N, can I somehow use that?”

Then it clicked:

I could create buckets where index = frequency.
The most frequent numbers would naturally end up in the highest index buckets, and I could just iterate from the back to grab the top k.
This way, I avoid sorting entirely, keeping it O(N) time! 🎯

🏆 My Optimized Approach: Bucket Sort

🔹 Steps to Solve Using Bucket Sort

Count frequencies of each number using a HashMap<Int, Int>.
Group numbers by frequency in an array (countArray), where index = frequency.
Collect the top k elements by iterating from the highest frequency bucket.

💻 Code Implementation (Kotlin)

class Solution { fun topKFrequent(nums: IntArray, k: Int): IntArray { val freqMap = HashMap<Int, Int>() for (n in nums) { freqMap[n] = freqMap.getOrDefault(n, 0) + 1 } val countArray = Array<MutableList<Int>>(nums.size + 1) { mutableListOf() } for ((num, freq) in freqMap) { countArray[freq].add(num) } val result = mutableListOf<Int>() for (i in countArray.size - 1 downTo 0) { // Iterate from highest frequency for (n in countArray[i]) { result.add(n) if (result.size == k) return result.toIntArray() } } return result.toIntArray() } } fun main() { val solution = Solution() // Example 1 val nums1 = intArrayOf(1, 1, 1, 2, 2, 3) val k1 = 2 val result1 = solution.topKFrequent(nums1, k1) println("Example 1:") println("Input: nums = [1, 1, 1, 2, 2, 3], k = 2") println("Output: [${result1.joinToString(", ")}]") println("Explanation: The elements 1 and 2 appear most frequently. 1 has a frequency of 3 and 2 has a frequency of 2.") // Example 2 val nums2 = intArrayOf(1, 2, 2, 3, 3, 3, 4, 4, 4, 4) val k2 = 2 val result2 = solution.topKFrequent(nums2, k2) println(" Example 2:") println("Input: nums = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], k = 2") println("Output: [${result2.joinToString(", ")}]") println("Explanation: The elements 4 and 3 appear most frequently. 4 has a frequency of 4 and 3 has a frequency of 3.") }

⏳ Time Complexity Analysis

Building freqMap → O(N)
Filling countArray → O(N)
Collecting top k elements → O(N) (worst case, when k ≈ N)
Overall Complexity: O(N) 🚀 (Fast & Efficient!)

🔥 What I Learned from This Struggle

✅ Sometimes sorting isn’t necessary—grouping data in a structured way can be more efficient.
✅ Thinking in terms of frequency instead of raw values led me to an intuitive solution.
✅ Iterating from the highest frequency made it easy to grab the most frequent elements.

This problem really forced me to rethink how I approach optimization, and I loved that moment when the bucket idea clicked! 🎯

Let’s embark on this coding journey together! If you have any questions or want to discuss other approaches to this problem, feel free to reach out.