# Solving 'top k frequent elements' using bucket sort

> an efficient approach to finding the k most frequent elements in an array

Published: 2025-04-01

## 📝 Problem Statement  
The problem [Top K Frequent Elements](https://leetcode.com/problems/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**  
1. **Count frequencies** of each number using a `HashMap<Int, Int>`.  
2. **Group numbers by frequency** in an array (`countArray`), where `index = frequency`.  
3. **Collect the top `k` elements** by iterating from the highest frequency bucket.  

---

## 💻 Code Implementation (Kotlin)  

```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("\nExample 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.