​

Top-K Elements

​

Approaches

​

1. Sorting

• Time: O(n log n)
• Simple but not optimal

​

2. Min/Max Heap of Size K

• K largest → use a min-heap of size K (pop smallest when size exceeds K)
• K smallest → use a max-heap of size K

import heapq

def top_k_largest(nums, k):
    return heapq.nlargest(k, nums)

# Manual approach with min-heap
def top_k_largest_heap(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap

• Time: O(n log k)
• Space: O(k)

​

3. Quickselect

• Time: O(n) average, O(n²) worst
• Space: O(1)
• Best when you need the k-th element, not all top K sorted

​

4. Bucket Sort (for frequency problems)

def top_k_frequent(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    result = []
    for i in range(len(buckets) - 1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]

• Time: O(n)

​

Which Approach to Use

​

Classic Problems

• Kth Largest Element in an Array
• Top K Frequent Elements
• Top K Frequent Words
• K Closest Points to Origin
• Find K Pairs with Smallest Sums
• Sort Characters by Frequency
• Reorganize String
• K Closest Elements in Sorted Array