Skip to content
Hello Python
Pattern1 Practice3 Interview

Top K

Keep only the best k candidates with a heap, quickselect, counting, or bucket strategy. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Top K when the prompt's constraints and required operations match this shape: Keep only the best k candidates with a heap, quickselect, counting, or bucket strategy.

Pybit demonstrates the Top K decision pattern in a professional coding interview workspace.
On this page · Keep Only the Best K Candidates

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Top K Code Labs

Keep Only the Best K Candidates

A size-k min-heap summarizes the current winners. Items weaker than its root cannot belong to the final top k, so the algorithm never needs to retain them.

Define the Heap Root

For k largest values, the min-heap root is the weakest current winner. For k smallest, use an inverted max-heap. State this meaning before choosing push, replace, or comparison direction.

Trace a Size-K Heap

Reference
import heapq

def top_k_trace(values,k):
    heap=[]; trace=[]
    for value in values:
        if len(heap)<k: heapq.heappush(heap,value)
        elif k and value>heap[0]: heapq.heapreplace(heap,value)
        trace.append(sorted(heap))
    return trace
Practice

Implement top_k_trace(values, k). Return the sorted min-heap contents after each input value is considered.

Public tests

  • Keep the root as the weakest winner

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Replace Only When Better

Fill the heap to k, then replace the root only when a new candidate is stronger. Heap replacement costs O(log k), giving O(n log k) time and O(k) working space.

Return the K Largest Values

Reference
import heapq

def k_largest(values,k):
    heap=[]
    for value in values:
        if len(heap)<k: heapq.heappush(heap,value)
        elif k and value>heap[0]: heapq.heapreplace(heap,value)
    return sorted(heap,reverse=True)
Practice

Implement k_largest(values,k). Return the k largest values in descending order without mutating input.

Public tests

  • Return only the strongest candidates

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose a Heap or Full Sorting

Use a heap when k is much smaller than n or values stream incrementally. Full sorting is simpler when all ranks are needed or k approaches n. Quickselect can give average O(n) selection but does not directly order the winners.

Explain It in an Interview

Say: “The root is the weakest of the current k winners. Anything no better than it can be discarded; a stronger candidate replaces it.” Include k=0, duplicates, output ordering, and the O(n log k) bound.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Top K invariant is independent of a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Top K decision loopO(n log k + k log k)O(n log k + k log k)Use a size-k max-heap represented by negated values, replacing its largest candidate when a smaller stream value arrives.

Space

O(k) for the focused Keep the K Smallest Stream Values implementation.

Assumptions

  • After each item the heap contains the k smallest values seen so far: items are added until full, and thereafter only a value smaller than the current selected maximum can improve the set.
  • The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

  1. State the precise Top K invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Heap size never exceeds k.
  3. Every discarded value is no better than all retained candidates at discard time.
  4. Maintain only k candidates in a bounded heap. Preserve this property after every transition.
  5. Use negated values to emulate a max-heap with heapq. Preserve this property after every transition.

When To Use Or Avoid Top K

Use It When

  • Use Top K when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
  • Use it when heap size never exceeds k.

Choose Another Tool When

  • Avoid Top K when its decision rule cannot eliminate work or preserve the required state.
  • Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Keep the K Smallest Stream Values before optimizing.

Avoid

def k_smallest_values(values, k):
    pass

Use instead

import heapq

def k_smallest_values(values, k):
    if k == 0:
        return []
    candidates = []
    for value in values:
        if len(candidates) < k:
            heapq.heappush(candidates, -value)
        elif value < -candidates[0]:
            heapq.heapreplace(candidates, -value)
    return sorted(-value for value in candidates)

Where you will hit this: Keep the K Smallest Stream Values(opens in a new tab)

Breaking the maintained state

Uses a min-heap and ejects the smallest candidate, producing large values instead.

Prevent it: Use the public tests and preserve this state: Heap size never exceeds k.

Avoid

import heapq
def k_smallest_values(values,k):
    h=[]
    for v in values:
        heapq.heappush(h,v)
        if len(h)>k: heapq.heappop(h)
    return sorted(h)

Use instead

import heapq

def k_smallest_values(values, k):
    if k == 0:
        return []
    candidates = []
    for value in values:
        if len(candidates) < k:
            heapq.heappush(candidates, -value)
        elif value < -candidates[0]:
            heapq.heapreplace(candidates, -value)
    return sorted(-value for value in candidates)

Where you will hit this: Keep the K Smallest Stream Values(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n log k + k log k).

Avoid

import heapq
def k_smallest_values(values,k):
    h=[]
    for v in values:
        heapq.heappush(h,v)
        if len(h)>k: heapq.heappop(h)
    return sorted(h)

Use instead

import heapq

def k_smallest_values(values, k):
    if k == 0:
        return []
    candidates = []
    for value in values:
        if len(candidates) < k:
            heapq.heappush(candidates, -value)
        elif value < -candidates[0]:
            heapq.heapreplace(candidates, -value)
    return sorted(-value for value in candidates)

Where you will hit this: Kth Largest Element in an Array(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.