Find the Kth Largest Element

📌 Definition:

📖 Detailed Explanation:

A clean approach maintains a min-heap of size k: push elements and evict the smallest whenever the heap exceeds k, so the root ends as the kth largest — O(n log k). Sorting is O(n log n); Quickselect averages O(n). Discuss the trade-off.

💻 Solutions:

• Java
• JavaScript
• Python

public static int kthLargest(int[] a, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap
    for (int x : a) {
        heap.offer(x);
        if (heap.size() > k) heap.poll();
    }
    return heap.peek();
}

function kthLargest(a, k) {
  // simple: sort descending and index (O(n log n))
  return [...a].sort((x, y) => y - x)[k - 1];
}

import heapq

def kth_largest(a, k):
    return heapq.nlargest(k, a)[-1]

🔑 Key Points:

• Min-heap of size k -> root is kth largest
• O(n log k), better than full sort for small k
• Quickselect averages O(n)
• Clarify distinct vs positional kth

🌍 Real-World Example: