NUHMAN.com

🧩 Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements.

You must solve it in O(n log n) time or better.

🔢 Example

python

Input: nums = [1,1,1,2,2,3], k = 2  
Output: [1,2]

Input: nums = [1], k = 1  
Output: [1]

✅ Constraints

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• k is in the range [1, number of unique elements in nums]

💡 Key Ideas

We have two main efficient strategies:

1. Heap (Min-Heap of size k) – Time: O(n log k)
2. Bucket Sort – Time: O(n)

We’ll walk through both.

✅ Method 1: Min-Heap (Using heapq)

🔧 Approach

1. Count frequencies using a Counter
2. Push (frequency, number) into a min-heap
3. Keep the heap size ≤ k
4. Extract top k frequent elements

🐍 Python Code (Min-Heap)

python

import heapq
from collections import Counter

class Solution:
    def topKFrequent(self, nums, k):
        count = Counter(nums)
        heap = []

        for num, freq in count.items():
            heapq.heappush(heap, (freq, num))
            if len(heap) > k:
                heapq.heappop(heap)

        return [num for freq, num in heap]

✅ Method 2: Bucket Sort

🔧 Approach

1. Count frequencies with Counter
2. Create a list of buckets where index = frequency
3. Fill buckets with numbers having that frequency
4. Traverse buckets in reverse order and collect top k

🐍 Python Code (Bucket Sort – O(n))

python

from collections import Counter

class Solution:
    def topKFrequent(self, nums, k):
        count = Counter(nums)
        freq = [[] for _ in range(len(nums) + 1)]

        for num, c in count.items():
            freq[c].append(num)

        result = []
        for i in range(len(freq) - 1, 0, -1):
            for num in freq[i]:
                result.append(num)
                if len(result) == k:
                    return result

🔍 Example Walkthrough: nums = [1,1,1,2,2,3], k = 2

• Frequencies: {1: 3, 2: 2, 3: 1}
• Bucket:
• freq[1] = [3]
• freq[2] = [2]
• freq[3] = [1]
• Traverse from end:
• Pick 1 from freq[3]
• Pick 2 from freq[2] → Done

Output: [1, 2]

⏱️ Time & Space Complexity

MethodTimeSpaceMin-HeapO(n log k)O(n + k)Bucket SortO(n)O(n)

🧠 Use Cases

• Social media: top-k trending hashtags
• E-commerce: top-k purchased items
• Search engines: most frequent queries

✅ Conclusion

LeetCode 347: Top K Frequent Elements is a classic problem for learning about heaps, hashmaps, and bucket sort. The bucket sort approach shines here for its linear time performance.

Use this to boost your confidence with frequency-based problems in interviews!