Introduction to Top K Frequent Elements
The Top K Frequent Elements problem is one of the most common algorithmic challenges you'll encounter in coding interviews and real-world data processing tasks. Given an array of integers and an integer k, the goal is to return the k most frequent elements in the array. While the problem statement sounds deceptively simple, there are multiple ways to solve it—each with different trade-offs in time and space complexity.
In this tutorial, we'll walk through several approaches to solve this problem in Python, starting from the brute-force method and building up to the most optimal solutions. By the end, you'll understand not only how to implement each solution but also when to choose one over the other.
Understanding the Problem
Before diving into solutions, let's clearly define the problem. Given an input array like [1, 1, 1, 2, 2, 3] and k = 2, we need to return the two elements that appear most frequently. In this case, element 1 appears three times and element 2 appears twice, so the answer would be [1, 2]. The order of the output does not matter unless explicitly specified.
Here are a few key constraints to keep in mind:
- The input array can contain duplicates.
kis always a valid integer between 1 and the number of unique elements.- The output can be returned in any order.
- You may assume the time complexity must be better than O(n log n), where n is the array size.
Why This Problem Matters
The Top K Frequent Elements problem is more than just an interview exercise. It has practical applications across many domains:
- Search engines: Finding the most queried terms in a given time window.
- Recommendation systems: Identifying the most popular items or products.
- Log analysis: Detecting the most frequent error codes or IP addresses in server logs.
- Natural language processing: Extracting the most common words from a corpus.
- Network monitoring: Identifying top talkers or most active connections.
Understanding how to efficiently solve this problem equips you with techniques like hash maps, heap-based selection, and bucket sorting—all of which are transferable to many other algorithmic challenges.
Approach 1: Using Counter and Sorting
The most straightforward approach is to count the frequency of each element using a hash map (or Python's Counter), then sort the elements by frequency and return the top k. This approach is easy to implement and understand, making it a great starting point.
Implementation
from collections import Counter
from typing import List
def top_k_frequent_sort(nums: List[int], k: int) -> List[int]:
# Count the frequency of each element
count = Counter(nums)
# Sort elements by frequency in descending order
sorted_elements = sorted(count.keys(), key=lambda x: count[x], reverse=True)
# Return the top k elements
return sorted_elements[:k]
# Example usage
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(top_k_frequent_sort(nums, k)) # Output: [1, 2]
Complexity Analysis
The time complexity of this approach is O(n + u log u), where n is the number of elements in the array and u is the number of unique elements. The sorting step dominates the complexity. The space complexity is O(u) for storing the frequency map and the sorted list.
While this solution works, it may not be the most efficient when dealing with large datasets, especially when k is much smaller than the number of unique elements.
Approach 2: Using a Min-Heap
A more efficient approach when k is small relative to the number of unique elements is to use a min-heap. The idea is to maintain a heap of size k that always contains the k most frequent elements seen so far. Python's heapq module makes this straightforward.
Implementation
import heapq
from collections import Counter
from typing import List
def top_k_frequent_heap(nums: List[int], k: int) -> List[int]:
# Count the frequency of each element
count = Counter(nums)
# Use a min-heap to keep track of the top k frequent elements
# We store tuples of (frequency, element) in the heap
heap = []
for element, freq in count.items():
heapq.heappush(heap, (freq, element))
# If heap size exceeds k, remove the smallest frequency element
if len(heap) > k:
heapq.heappop(heap)
# Extract the elements from the heap
return [element for freq, element in heap]
# Example usage
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(top_k_frequent_heap(nums, k)) # Output: [1, 2]
Complexity Analysis
The time complexity is O(n + u log k), where n is the number of elements and u is the number of unique elements. Since we only maintain a heap of size k, each push and pop operation takes O(log k) time. The space complexity is O(u + k) for the frequency map and the heap.
This approach is particularly efficient when k is small, as the heap operations become very fast. However, when k is close to u, the performance advantage over sorting diminishes.
Alternative: Using nlargest
Python's heapq module also provides a convenient nlargest function that internally uses a heap:
import heapq
from collections import Counter
from typing import List
def top_k_frequent_nlargest(nums: List[int], k: int) -> List[int]:
count = Counter(nums)
# nlargest returns the k largest elements based on the key function
return heapq.nlargest(k, count.keys(), key=count.get)
# Example usage
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(top_k_frequent_nlargest(nums, k)) # Output: [1, 2]
This is more concise and leverages the same underlying heap mechanism, but with cleaner syntax.
Approach 3: Bucket Sort (Optimal Solution)
The most optimal solution for this problem uses a bucket sort approach. The key insight is that the frequency of any element cannot exceed n (the total number of elements). We can create an array of buckets where the index represents the frequency, and each bucket contains the elements that have that frequency.
Implementation
from collections import Counter
from typing import List
def top_k_frequent_bucket(nums: List[int], k: int) -> List[int]:
# Count the frequency of each element
count = Counter(nums)
# Create buckets where index represents frequency
# The maximum frequency is len(nums)
bucket = [[] for _ in range(len(nums) + 1)]
for element, freq in count.items():
bucket[freq].append(element)
# Collect elements from highest frequency bucket downwards
result = []
for freq in range(len(bucket) - 1, 0, -1):
for element in bucket[freq]:
result.append(element)
if len(result) == k:
return result
return result
# Example usage
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(top_k_frequent_bucket(nums, k)) # Output: [1, 2]
Complexity Analysis
The time complexity of this approach is O(n), making it the most efficient solution. We iterate through the array once to count frequencies (O(n)), then iterate through the buckets (O(n) in the worst case since there are at most n buckets). The space complexity is O(n) for the frequency map and the bucket array.
This linear time complexity is possible because bucket sort avoids the comparison-based sorting lower bound of O(n log n) by using frequencies as direct indices.
Approach 4: Quickselect Algorithm
Another interesting approach is the Quickselect algorithm, which is based on the partitioning technique used in Quicksort. This algorithm has an average time complexity of O(n) but a worst-case of O(n²). It's worth knowing as it demonstrates an important algorithmic paradigm.
Implementation
from collections import Counter
from typing import List
import random
def top_k_frequent_quickselect(nums: List[int], k: int) -> List[int]:
count = Counter(nums)
unique = list(count.keys())
def partition(left, right, pivot_index):
pivot_freq = count[unique[pivot_index]]
# Move pivot to the end
unique[pivot_index], unique[right] = unique[right], unique[pivot_index]
store_index = left
for i in range(left, right):
if count[unique[i]] < pivot_freq:
unique[store_index], unique[i] = unique[i], unique[store_index]
store_index += 1
# Move pivot to its final place
unique[right], unique[store_index] = unique[store_index], unique[right]
return store_index
def quickselect(left, right, k_smallest):
if left == right:
return
# Select a random pivot index
pivot_index = random.randint(left, right)
pivot_index = partition(left, right, pivot_index)
if k_smallest == pivot_index:
return
elif k_smallest < pivot_index:
quickselect(left, pivot_index - 1, k_smallest)
else:
quickselect(pivot_index + 1, right, k_smallest)
# We want the k largest, so we look for (n - k) smallest
n = len(unique)
quickselect(0, n - 1, n - k)
return unique[n - k:]
# Example usage
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(top_k_frequent_quickselect(nums, k)) # Output: [1, 2]
Complexity Analysis
The average time complexity is O(n) with O(n²) in the worst case, though randomizing the pivot makes the worst case extremely unlikely. The space complexity is O(u) for the frequency map and the unique elements list, plus O(log u) for the recursion stack in the average case.
Comparing All Approaches
Let's summarize the different approaches and their complexities:
- Sorting: O(n + u log u) time, O(u) space — simplest to implement, good for small datasets.
- Min-Heap: O(n + u log k) time, O(u + k) space — best when k is much smaller than u.
- Bucket Sort: O(n) time, O(n) space — optimal for most cases, especially when frequencies are well distributed.
- Quickselect: O(n) average time, O(u) space — good theoretical approach but more complex to implement correctly.
Best Practices
When solving the Top K Frequent Elements problem, keep these best practices in mind:
- Choose the right approach based on your data: If
kis small, use a heap. If you need guaranteed linear time, use bucket sort. If simplicity matters most, use sorting. - Leverage Python's built-in tools: The
collections.Counterclass is highly optimized and should be your first choice for frequency counting. - Handle edge cases: Always consider what happens when the array is empty, when
kequals the number of unique elements, or when all elements are the same. - Consider memory constraints: If memory is limited, the heap approach uses less additional space than bucket sort.
- Test with large inputs: Performance differences become significant with large datasets, so always benchmark with realistic data sizes.
- Use type hints: Adding type hints improves code readability and helps catch errors early, as shown in all our examples.
Handling Edge Cases
Here's a robust version that handles common edge cases:
from collections import Counter
from typing import List
def top_k_frequent_robust(nums: List[int], k: int) -> List[int]:
# Edge case: empty array
if not nums:
return []
# Edge case: k equals number of unique elements
count = Counter(nums)
if k >= len(count):
return list(count.keys())
# Use bucket sort for optimal performance
bucket = [[] for _ in range(len(nums) + 1)]
for element, freq in count.items():
bucket[freq].append(element)
result = []
for freq in range(len(bucket) - 1, 0, -1):
for element in bucket[freq]:
result.append(element)
if len(result) == k:
return result
return result
# Test with various inputs
print(top_k_frequent_robust([], 2)) # Output: []
print(top_k_frequent_robust([1], 1)) # Output: [1]
print(top_k_frequent_robust([1, 1, 1, 1], 1)) # Output: [1]
print(top_k_frequent_robust([1, 2, 3, 4], 4)) # Output: [1, 2, 3, 4]
Performance Benchmarking
To help you choose the right approach, here's a simple benchmarking script that compares all methods:
import time
import random
from collections import Counter
import heapq
def benchmark_approaches():
# Generate test data
n = 100000
nums = [random.randint(1, 1000) for _ in range(n)]
k = 10
# Benchmark sorting approach
start = time.time()
count = Counter(nums)
sorted(count.keys(), key=lambda x: count[x], reverse=True)[:k]
print(f"Sorting: {time.time() - start:.4f}s")
# Benchmark heap approach
start = time.time()
count = Counter(nums)
heapq.nlargest(k, count.keys(), key=count.get)
print(f"Heap: {time.time() - start:.4f}s")
# Benchmark bucket sort approach
start = time.time()
count = Counter(nums)
bucket = [[] for _ in range(len(nums) + 1)]
for element, freq in count.items():
bucket[freq].append(element)
result = []
for freq in range(len(bucket) - 1, 0, -1):
for element in bucket[freq]:
result.append(element)
if len(result) == k:
break
if len(result) == k:
break
print(f"Bucket Sort: {time.time() - start:.4f}s")
benchmark_approaches()
Running this benchmark will give you a practical sense of how each approach performs with real data. Typically, you'll find that the bucket sort and heap approaches outperform the sorting method, especially as the dataset grows.
Conclusion
The Top K Frequent Elements problem is a fundamental algorithmic challenge that tests your ability to work with hash maps, heaps, and sorting techniques. Throughout this tutorial, we explored four distinct approaches—sorting, min-heap, bucket sort, and quickselect—each with its own strengths and trade-offs. The bucket sort approach stands out as the optimal solution with O(n) time complexity, while the heap-based method excels when k is small relative to the number of unique elements. By understanding all these approaches and their complexity characteristics, you'll be well-equipped to tackle not only this problem but also many related challenges in data processing, analytics, and system design. Remember to always consider your specific use case, data size, and performance requirements when choosing which approach to implement in your projects.