The k-th biggest reading

Heaps and priority queues Mid-level Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Fill the blank

Fill the blank so the heap holds the 3 biggest values.

Python 3.13
import heapq
keep: list[int] = []
for r in [3, 6, 9, 1, 8, 4]:
    heapq.heappush(keep, r)
    if ____:
        heapq.heappop(keep)
print(sorted(keep), keep[0])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A len(keep) > 3

Right: as soon as there are four, the smallest of them goes.

Capping the heap at k items is what turns O(n log n) into O(n log k).

Why not the others?
  • B len(keep) >= 3. That pops when there are three, leaving only two.
  • C r > keep[0]. That pops whenever the new value is not the smallest, not when there are too many, so the late 4 stays and it prints [4, 8, 9] 4.

30-second answer

Keep a min-heap of the k largest values seen so far. Push each reading; when the heap grows past k, pop its smallest. At the end the heap's root holds the k-th largest. O(n log k) time and O(k) memory, and it works on a stream.

Practise saying it · 45 s. No recording, just a timer

Explain the size-k heap for the k-th largest.

Say your answer out loud, then check which of these points you covered:

  • Min-heap of size k
  • Pop when over k
  • O(n log k)

Deep dive

This is the top-k template: a min-heap of size k for the largest, a max-heap of size k for the smallest.

Sorting is O(n log n) and fine when n is small or you need all values in order.

Quickselect averages O(n) but is O(n²) in the worst case and changes the input.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from heapq import heappop, heappush


def kth_largest(readings: list[int], k: int) -> int:
    keep: list[int] = []  # the k biggest so far; smallest on top
    for r in readings:
        heappush(keep, r)
        if len(keep) > k:
            heappop(keep)  # drop the smallest of k + 1
    return keep[0]

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
import java.util.PriorityQueue

fun kthLargest(readings: List<Int>, k: Int): Int {
    val keep = PriorityQueue<Int>() // smallest of the k biggest on top
    for (r in readings) {
        keep.add(r)
        if (keep.size > k) keep.poll()
    }
    return keep.peek()
}

Common mistakes

  • Using a max-heap of all n values, which costs O(n) memory and O(n + k log n) time.
  • Returning the largest item of the size-k heap instead of its smallest.

Senior take & follow-ups

Compare the three options (sort, heap, quickselect) in one sentence each.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you handle a stream where queries come between additions?

    Show hint

    Keep the same size-k heap; each query reads the top in O(1).

  2. When is quickselect better?

    Show hint

    For one query on a big in-memory list where average O(n) matters and mutation is fine.

What each operation costs: Min Heap · Max Heap · Heap Operations · Priority Queue

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.