Top K Elements Pattern: Heap vs Quickselect vs Bucket Sort

The top k elements pattern finds the k largest, smallest, most frequent or closest items without fully sorting, most often by keeping a heap of size k so the work is O(n log k) instead of O(n log n). Use it whenever a problem says "top k," "k most frequent," "k closest" or "kth largest," and know the two faster options for interview follow-ups: quickselect (average O(n)) and bucket sort (O(n) when the keys are bounded counts).

This guide is about choosing between those three tools. For how heaps themselves work (min-heap vs max-heap, merging k lists, the median of a stream), see the heap and priority queue pattern. Every Python snippet below was run against test cases before we published it.

When to use the top k elements pattern

• The answer is a small subset ranked by some key. "Return the k most frequent," "the k closest points," "the kth largest."
• Full sorting would work but is more than you need. If n is large and k is small, O(n log k) is much less work than O(n log n).
• A follow-up demands better than O(n log n). LeetCode 347's follow-up says exactly that. Bucket sort or quickselect is the expected next step.
• Data arrives as a stream. A size-k heap is the only option of the three that works when you cannot see all the data at once (Kth Largest Element in a Stream).
• Ties need a rule. "Sort words with the same frequency alphabetically" means your comparison key needs two parts.

Heap vs quickselect vs bucket sort: which to use

In an interview, say the sort baseline, code the heap, then offer quickselect or bucket sort if the interviewer asks for better. That order shows you know the trade-offs without overcomplicating the first solution.

The top k elements template in Python

Python's heapq is a min-heap. To keep the k largest items, keep a min-heap of size k: its root is the smallest of your current top k, so it is the one to evict when something bigger arrives.

import heapq

def top_k_largest(nums, k):
    heap = []                          # min-heap of the k largest so far
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)        # evict the smallest of the k + 1
    return heap                        # heap[0] is the kth largest

Flip it for the k smallest: push -x (a max-heap by negation) and evict the largest. In real code, heapq.nlargest(k, nums) and heapq.nsmallest(k, nums) do this for you in O(n log k), and both accept a key= argument. Interviewers usually want to see the manual version once, then accept the library call.

Worked problems

1. Top K Frequent Elements (LeetCode 347, Medium): heap and bucket sort

Problem: return the k most frequent values in any order. The follow-up requires better than O(n log n). See Top K Frequent Elements.

Idea: count with a Counter, then pick the top k counts. The heap version is O(n log k). The bucket version uses the fact that a frequency is between 1 and n: put each value in a bucket indexed by its count, then read the buckets from high to low.

from collections import Counter
import heapq

def top_k_frequent_heap(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

def top_k_frequent_bucket(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]   # index = frequency
    for num, freq in count.items():
        buckets[freq].append(num)
    result = []
    for freq in range(len(nums), 0, -1):
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result
    return result

Time: heap O(n log k), bucket O(n). Space: O(n) for the counter in both.

2. Top K Frequent Words (LeetCode 692, Medium): ties need a rule

Problem: return the k most frequent words, sorted by frequency from high to low, with ties broken alphabetically. The follow-up asks for O(n log k) time.

Idea: the ranking key is "higher count first, then alphabetical." As a single sortable key that is (-count, word), and the k smallest keys are the answer, already in the required order.

from collections import Counter
import heapq

def top_k_frequent_words(words, k):
    count = Counter(words)
    return heapq.nsmallest(k, count, key=lambda w: (-count[w], w))

If the interviewer wants the manual size-k heap, the trap is the eviction order. The root must be the entry you would drop first: the lowest count, and on a tie the word that comes later alphabetically. Plain tuples cannot express "reverse alphabetical" for strings, so define the comparison yourself:

class Entry:
    def __init__(self, freq, word):
        self.freq, self.word = freq, word

    def __lt__(self, other):           # True means "evict self first"
        if self.freq != other.freq:
            return self.freq < other.freq
        return self.word > other.word  # later in the alphabet loses ties

def top_k_frequent_words_manual(words, k):
    heap = []
    for word, freq in Counter(words).items():
        heapq.heappush(heap, Entry(freq, word))
        if len(heap) > k:
            heapq.heappop(heap)
    result = []
    while heap:
        result.append(heapq.heappop(heap).word)
    return result[::-1]                # popped worst-first, so reverse

Time: O(n log k) for both versions after counting. Space: O(n) for the counter.

3. Kth Largest Element in an Array (LeetCode 215, Medium): quickselect

Problem: return the kth largest value (by sorted position, not the kth distinct value). The problem asks: can you solve it without sorting? The heap guide solves it with a size-k heap; this is the average O(n) answer.

Idea: the kth largest sits at index n - k in ascending order. Partition around a random pivot into "less," "equal" and "greater," then keep only the side that contains that index. A three-way partition matters: with many equal values, a two-way partition can degrade to O(n²).

import random

def find_kth_largest(nums, k):
    target = len(nums) - k             # index in ascending order
    lo, hi = 0, len(nums) - 1
    while True:
        pivot = nums[random.randint(lo, hi)]
        lt, i, gt = lo, lo, hi         # < pivot | == pivot | > pivot
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1
        if target < lt:
            hi = lt - 1
        elif target > gt:
            lo = gt + 1
        else:
            return pivot               # target falls in the "equal" block

Time: O(n) on average, O(n²) in the worst case (a random pivot makes that very unlikely). Space: O(1) extra, because the loop is iterative. It rearranges the input, so copy the array first if the caller needs it unchanged. After it returns, the k largest values occupy nums[n - k:], which also answers "top k, any order."

Common bugs and edge cases

• Wrong heap direction. For the k largest, keep a min-heap of size k. A max-heap of everything works but costs O(n) space and O(k log n) pops.
• Comparing tuples that contain non-comparable items. Pushing (dist, point) where two distances tie makes Python compare the second items; lists compare fine, but dicts or custom objects raise TypeError. Add an index as a tiebreaker: (dist, i, point).
• Kth largest vs kth distinct. LeetCode 215 counts duplicates. Do not deduplicate first.
• Tie order in the output. When the problem specifies an order for ties (692), test a case with equal counts.
• Bucket array size. Frequencies go up to n, so the bucket list needs n + 1 slots.
• Quickselect on sorted or all-equal input with a fixed pivot is the O(n²) case. Randomize, and use three-way partitioning.

Practice list: 10 top k elements problems

Difficulty labels are LeetCode's own, checked as of October 2026.

For streaming medians, the two heaps pattern builds on the same heap skills. For more patterns see 15 LeetCode patterns for interviews, binary search patterns (for problem 658) and the coding interview cheat sheet. The Big-O complexity visualizer shows how n log k compares with n log n.

How to practice the top k elements pattern

Solve 347 three ways (sort, heap, bucket) and 215 two ways (heap, quickselect), then explain out loud when you would pick each. Being able to compare approaches clearly is what separates a strong answer from a correct one.

CoPilot Interview's Mock Interview can run a coding round from your résumé and the job description and score each spoken answer out of 10 with what to fix and a model answer. The browser AI mock interview needs no install and includes a coding track.

FAQ

What is the top k elements pattern?

It is a family of techniques for returning the k largest, smallest, most frequent or closest items without sorting everything. The default is a heap of size k, which runs in O(n log k); quickselect and bucket sort are faster alternatives for specific cases.

Why use a min-heap to find the k largest elements?

A min-heap of size k keeps the smallest of your current top k at the root. When a new value is larger than that root, you pop the root and push the new value, so the heap always holds the k largest seen so far, using only O(k) space.

What is the time complexity of the top k elements pattern?

A size-k heap is O(n log k) time and O(k) space. Quickselect is O(n) on average and O(n squared) in the worst case with O(1) extra space. Bucket sort by frequency is O(n) time and O(n) space. Sorting everything is O(n log n).

When is quickselect better than a heap?

When you have the whole array in memory, may modify it, and only need the kth element or an unordered top k. It averages O(n). A heap is better for streams, when the input must stay unchanged, or when you need the top k in sorted order.

How do I solve Top K Frequent Elements in better than O(n log n)?

Count frequencies, then place each value in a bucket indexed by its frequency, which is at most n. Read buckets from the highest frequency down until you have k values. That is O(n) time and O(n) space.

Which LeetCode problems use the top k elements pattern?

Kth Largest Element in an Array (215), Top K Frequent Elements (347), Top K Frequent Words (692), K Closest Points to Origin (973), Kth Largest Element in a Stream (703), Sort Characters By Frequency (451), Find K Closest Elements (658) and Reorganize String (767).