vizlearn

Kth largest element

Interview QuestionsBy Updated

Keep a min-heap of size k. Each value either beats the smallest kept one and replaces it, or is discarded immediately. The heap's root is the answer. O(n log k) time and O(k) memory — which matters when n is enormous and k is ten.

Overview

Three answers, and the reason to choose

Sort and index. sorted(a)[-k]. O(n log n), one line, and the right answer in real code for any array that fits in memory.

Min-heap of size k. O(n log k) time and O(k) memory. The only one that works on a stream, or when n is far larger than memory.

Quickselect. O(n) average by partitioning and recursing into one side only. O(n²) worst case with a bad pivot, fixable with a random one.

Interviewers are usually listening for whether you notice the heap is bounded by k rather than n.

Lists & arraysCoding problemMedium

Step through it

What to watch

  • The heap never grows beyond k — that is the memory bound.
  • A value smaller than the root is discarded without being stored.
  • The root is always the smallest of the k largest.

Say this out loud

"Min-heap of size k: O(n log k) time, O(k) space. Sorting is O(n log n) and quickselect is O(n) average but O(n²) worst case. For a stream, or when n doesn't fit in memory, the heap is the only one that works."

Kth largest element

Find the kth largest element in an unsorted array.

Why a min-heap for the largest

It feels backwards and it is the key idea. To keep the k largest values you need constant-time access to the smallest of the ones you kept, because that is the one to evict when something better arrives. A min-heap puts exactly that at the root.

Once the heap is full, a value below the root cannot be in the top k, so it is discarded without being stored at all.

Quickselect, briefly

Partition around a pivot as quicksort does, then recurse into only the side containing position k. Because one side is discarded each time, the expected work is n + n/2 + n/4 + ... = O(n).

Its worst case is O(n²) on a bad pivot sequence, so pick the pivot at random. Say that explicitly — "quickselect, with a random pivot" is a complete answer, and "quickselect" alone invites the follow-up about sorted input.

Run it in Python

All three approaches with the number of elements each one stores, then timed on a large array so the O(k) memory claim and the O(n) average are both visible.

kth_largest.pyPython 3
Output
How the code works
  1. heapq.heapreplace(heap, v)Pop the root and push the new value in one operation. Doing it as a pop then a push costs two sift operations instead of one and is the usual way to write this slightly wrong.
  2. elif v > heap[0]A value below the root cannot be in the top k, so it is discarded without ever being stored. That test is what keeps the memory at O(k).
  3. a MIN-heap for the LARGEST kThe counterintuitive part. Keeping the k largest requires constant-time access to the weakest of them, so it can be evicted — and a min-heap puts exactly that at the root.
  4. pivot = a[random.randint(lo, hi)]Quickselect's worst case is O(n²) on an adversarial pivot sequence. Choosing at random makes that vanishingly unlikely, and saying so out loud is part of the answer.
Change one thing
  • Set k = len(big). The heap now stores everything and the approach collapses back to sorting — the win is entirely in k being small.
  • Replace heapreplace with a push followed by a pop and compare the timings. Same answer, more sifting.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why a MIN-heap when you want the k LARGEST elements?
  2. The heap approach uses how much memory?
  3. Quickselect's worst case is:





 Cheat sheet
Kth largest element
Keep a min-heap of size k. Each value either beats the smallest kept one and replaces it, or is discarded immediately. The heap's root is the answer. O(n log k) time and O(k) memory — which matters when n is enormous and k is ten.
INTERVIEW · vizlearn.in/interview/kth-largest-element.html
More in Interview
InterviewTrapping rain waterInterviewSort an array of 0s, 1s and 2sInterview3SumInterviewSearch in a rotated sorted array
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact