← Bank
DSA

Kth Largest Element

DSAMid~13m
heapquickselectselection

Prompt

We score every request for risk and, periodically, want the kth highest score in the current batch — say the 10th-highest out of a few million. Given an unsorted array of scores and a k, find the kth largest, and tell me how you'd keep it efficient.

How this round runs

I'm holding back how big the batch gets and whether it's static or streaming — clarify before coding, because the right structure flips depending on the answer, and I'll change that assumption on you.

Model answer

Clarify first: how big is the array relative to k — is k small (top-10) or a fraction of n? Is the data static in an array, or arriving as a stream? Can I reorder the input in place, or must I leave it untouched?

Sorting and indexing is O(n log n) — fine as a baseline, but we can do better. Two real options with a trade-off:

A size-k min-heap: scan once, push each element, and pop the smallest whenever the heap exceeds k. The root is then the kth largest. O(n log k) time, O(k) space — and it works on a stream and never reorders the input.

function kthLargest(nums, k) {
  const heap = []; // min-heap of the k largest seen so far
  for (const x of nums) {
    push(heap, x);
    if (heap.length > k) pop(heap); // drop the current smallest
  }
  return heap[0];
}

Quickselect: partition around a pivot like quicksort, but recurse into only the side that contains rank k. O(n) average time, O(1) extra — but O(n^2) worst case on bad pivots, and it mutates the array, so it's an array-only, static-data move.

So: small k or streaming → the heap. One-shot, in-memory, k near n, want expected-linear → quickselect with a randomized pivot to dodge the worst case.

Signals — what a strong answer shows
  • Asked whether the data is static or streaming and how k compares to n
  • Named sort -> heap -> quickselect and gave the time/space for each
  • Picked the heap for streaming and explained the O(n log k), O(k) trade-off
  • Flagged quickselect's O(n^2) worst case and the randomized-pivot fix
Follow-ups — where it goes next
  • Now it's a stream and you can't hold all n → keep the size-k min-heap; it only ever stores k elements
  • You have a hard memory bound smaller than the array → heap wins (O(k)); quickselect needs the whole array resident
Study this: Data Types