QuestionsDSA

Kth Largest Element

Heap / Top-KMediumDSA

Return the k-th largest element in an unsorted array.

What it tests

Knowing a min-heap of size k beats sorting when k ≪ n — and JS has no built-in heap.

Approach & answer

Keep a min-heap of size k. The smallest of the k largest sits on top, so once the heap exceeds k you pop the min. The root is the answer. O(n log k) vs O(n log n) for a full sort. (In an interview, either implement a tiny binary heap or state you'd use one.) Know the alternatives too: Quickselect gives O(n) average time by partitioning around a pivot and recursing into only one side, though worst case is O(n²). The size-k heap wins when the data streams in or n is huge and k is small, because it caps memory at k. JavaScript still ships no built-in priority queue, so naming this gap and sketching the heap earns points.

Use this technique when

'Top K', 'K-th largest/smallest', 'K closest' → bounded heap of size k.

Complexity

Time O(n log k) · Space O(k)

References

js