LeetEye LeetEye
Easy Hash Set / Hash Map ~5 min

Top K Frequent Elements

arrays-and-hashing top-k-frequent-elements

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Examples

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

Step 1 is straightforward: hash map for frequency counting.

For 'top k by frequency': count with hash map, then either heap (O(n log k)) or bucket sort by frequency (O(n)).

How to Approach This Problem

Pattern Recognition: When you see keywords like top k frequent elements arrays-and-hashing, think Hash Set / Hash Map.

Step-by-Step Reasoning

1 What's the first thing you need to compute?
Answer: The frequency of each element
You can't find "most frequent" without knowing frequencies.
2 Best data structure for counting frequencies?
Answer: Hash map (for general case)
Hash map handles any value range efficiently. Array works too if values are small non-negative integers.
3 After counting frequencies, how do you find the top k?
Answer: All of the above
All work. They differ in time complexity: Sort is O(n log n), Heap is O(n log k), Bucket is O(n).
4 Why can we use bucket sort for this problem?
Answer: Frequencies have a bounded range (1 to n)
Bucket sort requires a bounded range. Frequency of any element is between 1 and n (total elements). This is a limited range we can bucket into.
5 In bucket sort approach, bucket[i] contains:
Answer: Elements that appear i times
We're bucketing by frequency, not by value. Bucket[3] holds all elements that appear exactly 3 times.
6 To get top k frequent, iterate buckets in which order?
Answer: Bucket n to bucket 0 (descending frequency)
We want most frequent first. Start from highest frequency bucket (n), work down until we've collected k elements.

Solution

def topKFrequent(nums: List[int], k: int) -> List[int]:
    # Step 1: Count frequencies
    count = Counter(nums)
    
    # Step 2: Bucket sort by frequency
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    
    # Step 3: Collect top k from highest buckets
    result = []
    for i in range(len(buckets) - 1, 0, -1):
        for num in buckets[i]:
            result.append(num)
            if len(result) == k:
                return result
    return result

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Hash Set / Hash Map problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye