Classic interview question with three correct answers at different complexities. The interviewer wants you to walk through them and pick.

Approach 1 — Sort

function kthLargest(arr, k) {
  return arr.slice().sort((a, b) => b - a)[k - 1];
}

• O(n log n) time, O(n) space.
• Simplest; fine if asked.

Approach 2 — Min-heap of size k

Maintain a heap of the k largest seen so far. Iterate; push; if size > k, pop the min. At the end, the min of the heap is the k-th largest.

function kthLargest(arr, k) {
  const heap = new MinHeap();
  for (const x of arr) {
    heap.push(x);
    if (heap.size > k) heap.pop();
  }
  return heap.peek();
}

• O(n log k) time, O(k) space.
• Great for streaming / very large arrays where k is small.

JavaScript doesn't have a built-in heap; implement or use a library.

Approach 3 — Quickselect

Partition around a pivot like quicksort, but only recurse into the side containing the k-th element.

function kthLargest(arr, k) {
  const target = arr.length - k;     // index of k-th largest in ascending sort
  arr = arr.slice();

  function select(lo, hi) {
    if (lo === hi) return arr[lo];
    const p = partition(lo, hi);
    if (p === target) return arr[p];
    if (p < target) return select(p + 1, hi);
    return select(lo, p - 1);
  }

  function partition(lo, hi) {
    const pivot = arr[hi];           // (use median-of-three or random for safety)
    let i = lo;
    for (let j = lo; j < hi; j++) {
      if (arr[j] < pivot) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
      }
    }
    [arr[i], arr[hi]] = [arr[hi], arr[i]];
    return i;
  }

  return select(0, arr.length - 1);
}

• Average O(n), worst O(n²) (mitigated by random pivot).
• O(log n) stack on average.
• Best when you'd otherwise sort the whole array.

Which to use in an interview

• Asked to optimize space / streaming → min-heap O(n log k).
• Asked for best average time → Quickselect O(n).
• Asked simplest → sort.

Lead with the heap answer — it's clean, easy to explain, and has predictable complexity. Mention Quickselect for "if we wanted average O(n)".

Edge cases

• k > arr.length → invalid; throw or return undefined.
• k = 1 → max; k = n → min.
• Duplicates — "k-th largest" usually counts duplicates as distinct positions.
• Empty array → invalid.

Quickselect pitfalls

• Always-bad pivot (sorted input + pivot = last) → O(n²). Use random pivot or median-of-three.
• In-place mutation — clone if the caller cares.

Interview framing

"Three approaches: sort and index — O(n log n), trivial. Min-heap of size k — O(n log k), O(k) space, best when k ≪ n or when streaming. Quickselect — average O(n), worst O(n²) with random pivot to mitigate, in-place. For the interview, I'd lead with the min-heap: predictable complexity, simple to explain, and clearly better than sort when k is small. If average O(n) matters, Quickselect is the way."