Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
nums = [1,1,1,2,2,3], k = 2
# Output: [1, 2] — 1 appears 3 times, 2 appears 2 times
Approach: Use a hash map to count frequencies, then use bucket sort — create buckets where index = frequency, and collect from highest bucket down.
This gives O(n) time vs O(n log n) for a sorting approach!
📋 Instructions
Implement `top_k_frequent(nums, k)` using a hash map + bucket sort approach.
Test with `nums = [1,1,1,2,2,3]` and `k = 2`.
Print the result as a sorted list: `[1, 2]`
Step 1: Count frequencies with a dict. Step 2: Create a list of empty lists with size len(nums)+1. Step 3: For each num,count pair, append num to bucket[count]. Step 4: Iterate buckets from end to start, collecting k elements.