Top K Frequent Elements - Python Solution

1. Introduction

"Top K Frequent Elements" is a common problem in data analysis and algorithm design, requiring efficient extraction of the most frequent elements from a collection. It tests one's ability to apply hash tables and heap (priority queue) structures to efficiently solve frequency-based problems.


Given an integer array nums and an integer k, the task is to return the k most frequent elements. The answer may be returned in any order.

2. Solution Steps

1. Create a hash table (dictionary in Python) to store the frequency of each element in nums.

2. Use a heap (or priority queue) to keep track of the k most frequent elements.

3. Iterate through the hash table and add each element-frequency pair to the heap.

4. If the heap size exceeds k, remove the element with the lowest frequency.

5. Extract the top k elements from the heap, which will be the most frequent elements.

6. Return these top k elements.

3. Code Program

import heapq
from collections import Counter

def topKFrequent(nums, k):
    if k == len(nums):
        return nums

    count = Counter(nums)  # Step 1
    return heapq.nlargest(k, count.keys(), key=count.get)  # Step 5 and 6

# Example Usage
print(topKFrequent([1,1,1,2,2,3], 2))
print(topKFrequent([1], 1))


[1, 2]


1. Frequency Count: The Counter class from the collections module is used to count the frequency of each element in nums.

2. Heap for Top Frequencies: A heap is used to store elements based on their frequencies.

3. Extracting Top K Elements: heapq.nlargest is used to retrieve the k elements with the highest frequency.

4. Efficient Computation: This method efficiently computes the most frequent elements using a min-heap and the Counter class.

5. Flexibility: The solution works for different sizes of nums and values of k.

6. Result: The function returns the k most frequent elements in nums.