Whenever a problem asks for the ”$k$ largest”, ”$k$ most frequent”, ”$k$ closest”, or ”$k$-th something”, your brain should immediately reach for one tool: a heap capped at size $k$. You almost never need to sort the whole input to answer a question about only $k$ of its elements — and that gap between “sort everything” and “just track the top $k$” is worth a full complexity class in an interview.

What you’ll learn

• How to recognize the top-k cue in a problem statement.
• The reusable template: a min-heap that never grows past size $k$.
• heapq.nlargestheapq.nlargest / heapq.nsmallestheapq.nsmallest — the one-line version of the same idea.
• Quickselect — the $O(n)$ average-case alternative, and its trade-offs.
• Why a size-$k$ heap beats a full sort: $O(n \log k)$ vs. $O(n \log n)$.

The cue: “top k”, “kth largest”, “k closest”

Any phrasing that only cares about $k$ elements out of $n$ — and doesn’t need the rest of the array in sorted order — is a signal to stop thinking “sort” and start thinking “heap of size $k$”. Sorting the entire array to read off the last $k$ elements does $O(n \log n)$ work to answer a question that only needs $O(n \log k)$.

The pattern: a min-heap capped at size k

To find the $k$ largest values, keep a min-heap (not a max-heap) of size $k$. Counterintuitive at first, but the reason is simple: the heap’s root (heap[0]heap[0]) is always the smallest of the k largest values seen so far — exactly the one value you’d want to evict the instant something bigger shows up.

import heapq
 
def top_k_largest(nums, k):
    min_heap = []
    for x in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, x)          # heap not full yet -- just add
        elif x > min_heap[0]:
            heapq.heapreplace(min_heap, x)       # x beats the current worst of the top-k
 
    return sorted(min_heap, reverse=True)
 
 
nums = [3, 2, 1, 5, 6, 4]
print(top_k_largest(nums, 2))   # expect [6, 5]

import heapq
 
def top_k_largest(nums, k):
    min_heap = []
    for x in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, x)          # heap not full yet -- just add
        elif x > min_heap[0]:
            heapq.heapreplace(min_heap, x)       # x beats the current worst of the top-k
 
    return sorted(min_heap, reverse=True)
 
 
nums = [3, 2, 1, 5, 6, 4]
print(top_k_largest(nums, 2))   # expect [6, 5]

At every point in the loop, min_heapmin_heap holds exactly the $k$ largest values seen so far, in no particular internal order — only min_heap[0]min_heap[0] (the smallest of them) is guaranteed to sit at the root.

How it works

Worked example: Top K Frequent Elements

Count occurrences with a CounterCounter, then let heapq.nlargestheapq.nlargest do the size-$k$ heap work for you, ranking by count instead of by raw value.

import heapq
from collections import Counter
 
def top_k_frequent(nums, k):
    counts = Counter(nums)
    return heapq.nlargest(k, counts.keys(), key=counts.get)
 
 
nums = [1, 1, 1, 2, 2, 3]
print(top_k_frequent(nums, 2))   # expect [1, 2] -- 1 appears 3x, 2 appears 2x

import heapq
from collections import Counter
 
def top_k_frequent(nums, k):
    counts = Counter(nums)
    return heapq.nlargest(k, counts.keys(), key=counts.get)
 
 
nums = [1, 1, 1, 2, 2, 3]
print(top_k_frequent(nums, 2))   # expect [1, 2] -- 1 appears 3x, 2 appears 2x

heapq.nlargest(k, iterable, key=...)heapq.nlargest(k, iterable, key=...) and heapq.nsmallest(k, iterable, key=...)heapq.nsmallest(k, iterable, key=...) are the built-in, one-line version of the exact pattern above — reach for them whenever you don’t need to hand-roll the heap yourself.

Quickselect: trading heap overhead for average O(n)

If you only need the $k$-th value itself (not the full sorted top-$k$), the Quickselect algorithm — a partition step borrowed from quicksort — finds it in $O(n)$ average time, faster than any heap-based approach for a single query.

import random
 
def kth_largest(nums, k):
    target_index = len(nums) - k   # k-th largest == (n-k)-th smallest, 0-indexed
 
    def partition(lo, hi):
        pivot_index = random.randint(lo, hi)
        pivot = nums[pivot_index]
        nums[pivot_index], nums[hi] = nums[hi], nums[pivot_index]   # move pivot to the end
        store = lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]   # pivot lands in its final sorted spot
        return store
 
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        p = partition(lo, hi)
        if p == target_index:
            return nums[p]
        elif p < target_index:
            lo = p + 1
        else:
            hi = p - 1
    return nums[lo]
 
 
nums = [3, 2, 1, 5, 6, 4]
print(kth_largest(nums, 2))   # expect 5

import random
 
def kth_largest(nums, k):
    target_index = len(nums) - k   # k-th largest == (n-k)-th smallest, 0-indexed
 
    def partition(lo, hi):
        pivot_index = random.randint(lo, hi)
        pivot = nums[pivot_index]
        nums[pivot_index], nums[hi] = nums[hi], nums[pivot_index]   # move pivot to the end
        store = lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]   # pivot lands in its final sorted spot
        return store
 
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        p = partition(lo, hi)
        if p == target_index:
            return nums[p]
        elif p < target_index:
            lo = p + 1
        else:
            hi = p - 1
    return nums[lo]
 
 
nums = [3, 2, 1, 5, 6, 4]
print(kth_largest(nums, 2))   # expect 5

Time and space complexity

When to use it

• The problem only cares about $k$ elements, and $k \ll n$ — a size-$k$ heap avoids paying for a full $O(n \log n)$ sort.
• The data arrives as a stream you can’t hold in memory all at once — a heap of size $k$ never grows past $k$ items.
• You need the top-$k$ ranked by a derived key (frequency, distance, custom score) rather than by raw value — pass key=key= to nlargestnlargest / nsmallestnsmallest.
• Reach for Quickselect instead when you need exactly one $k$-th value, the whole array already fits in memory, and average-case $O(n)$ matters more than worst-case guarantees.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 347 — Top K Frequent Elements · Medium

Problem. Return the kk most frequent elements, in any order. Your algorithm must be better than $O(n \log n)$.

Constraints. 1 <= len(nums) <= 10^51 <= len(nums) <= 10^5, kk is valid, and the answer is unique.

Examples. nums = [1,1,1,2,2,3], k = 2nums = [1,1,1,2,2,3], k = 2 gives [1,2][1,2] · nums = [1], k = 1nums = [1], k = 1 gives [1][1]

buckets = [[] for _ in range(len(nums) + 1)]
for value, count in Counter(nums).items():
    buckets[count].append(value)
out = []
for count in range(len(buckets) - 1, 0, -1):
    for value in buckets[count]:
        out.append(value)
        if len(out) == k:
            return out

buckets = [[] for _ in range(len(nums) + 1)]
for value, count in Counter(nums).items():
    buckets[count].append(value)
out = []
for count in range(len(buckets) - 1, 0, -1):
    for value in buckets[count]:
        out.append(value)
        if len(out) == k:
            return out

LC 658 — Find K Closest Elements · Medium

Problem. Given a sorted array, an integer kk and a value xx, return the kk closest elements to xx, sorted ascending. Ties prefer the smaller element.

Constraints. 1 <= k <= len(arr) <= 10^41 <= k <= len(arr) <= 10^4, arrarr sorted ascending, -10^4 <= arr[i], x <= 10^4-10^4 <= arr[i], x <= 10^4.

Examples. arr = [1,2,3,4,5], k = 4, x = 3arr = [1,2,3,4,5], k = 4, x = 3 gives [1,2,3,4][1,2,3,4] · arr = [1,2,3,4,5], k = 4, x = -1arr = [1,2,3,4,5], k = 4, x = -1 gives [1,2,3,4][1,2,3,4]

LC 1481 — Least Number of Unique Integers after K Removals · Medium

Problem. Remove exactly kk elements from the array to minimise the number of distinct integers remaining. Return that minimum.

Constraints. 1 <= len(arr) <= 10^51 <= len(arr) <= 10^5, 1 <= arr[i] <= 10^91 <= arr[i] <= 10^9, 0 <= k <= len(arr)0 <= k <= len(arr).

Examples. arr = [5,5,4], k = 1arr = [5,5,4], k = 1 gives 11 · arr = [4,3,1,1,3,3,2], k = 3arr = [4,3,1,1,3,3,2], k = 3 gives 22

LeetCode problem set

Recap

• The top-k cue: whenever a problem only needs $k$ of $n$ elements, resist sorting everything.
• A min-heap capped at size $k$ tracks the top-$k$ largest in $O(n \log k)$ total, using only $O(k)$ extra space.
• heapq.nlargestheapq.nlargest / nsmallestnsmallest give you the same pattern in one line, with an optional key=key= for ranking by a derived value.
• Quickselect trades the heap’s streaming ability for average-case $O(n)$, when you only need one $k$-th value from data already in memory.

Next: K-way Merge — the heap pattern for combining many sorted sequences into one.