Kth Largest Element
Mahabharata — The Elite Selection — Finding the kth Most Powerful Warrior
k-वां महत्तम — लघु-ढेर रखो k तत्वों का। शीर्षे सबसे छोटा — वही k-वां महत्तम॥
*kth largest — keep a min-heap of k elements. At the top stands the smallest among k largest — that is the kth largest.*
The Story
Find the kth largest element in an unsorted array.
For `nums=[3,2,1,5,6,4]`, k=2: answer=5. (Sorted descending: 6,5,4,3,2,1 → 2nd largest = 5)
**Min-Heap of size k:** - Maintain a min-heap of the k largest elements seen so far - For each element: add to heap - If heap size > k: remove the minimum (it's too small to be in top-k largest) - After processing: heap.peek() = kth largest
```java PriorityQueue<Integer> pq = new PriorityQueue<>(); // Min-heap (default) for (int n : nums) { pq.offer(n); if (pq.size() > k) pq.poll(); // Remove smallest } return pq.peek(); ```
Trace `[3,2,1,5,6,4]`, k=2: - Add 3,2: pq=[2,3] - Add 1: pq=[1,2,3], size=3>2 → poll=1 → pq=[2,3] - Add 5: pq=[2,3,5], size=3>2 → poll=2 → pq=[3,5] - Add 6: pq=[3,5,6], size=3>2 → poll=3 → pq=[5,6] - Add 4: pq=[4,5,6], size=3>2 → poll=4 → pq=[5,6] - Return peek()=5 ✓
The key insight: the min-heap of k largest elements has the SMALLEST of the top-k at its top. That's the kth largest — the boundary between top-k and the rest.
The Sort-and-Index Approach
Sort descending, return arr[k-1]. Or sort ascending, return arr[n-k]. O(n log n).
public int findKthLargestBruteForce(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}The Min-Heap-of-K-Largest Wisdom
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(); // Min-heap
for (int n : nums) {
pq.offer(n);
if (pq.size() > k) pq.poll();
}
return pq.peek();
}Step-by-Step Walkthrough
[5], k=1 Add 5: [5]. size=1≤1. Return 5 ✅
Deep Insight
**hp-1 vs hp-2 comparison:** | | hp-1 (kth smallest) | hp-2 (kth largest) | |---|---|---| | Heap type | MAX-heap | MIN-heap | | Keep | k smallest | k largest | | Peek | kth smallest | kth largest | | Poll when | size > k | size > k |
**Quick Select (Hoare's algorithm):** O(n) average, O(n²) worst. More efficient on average but doesn't handle streams (need all elements upfront).
**The heap approach handles streams:** Process elements one at a time, always maintaining the top-k. Useful when elements arrive one by one and you need to know the current kth largest at any point.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(1) | Sort |
| Optimal | O(n log k) | O(k) | n insertions into size-k heap |
Pattern Recognition
✅ kth largest → MIN-heap of size k ✅ Poll when size > k (removes the smallest in heap) ✅ heap.peek() = kth largest (smallest of top-k) ✅ Symmetric to hp-1 with opposite heap **LeetCode Trigger Phrases:** → "kth largest element in an array" → Maintain top k largest seen so far → Stream kth largest (LeetCode 703)
Bhagavad Gita 10.28
धनंजय।। तेजस्विनामहं वज्रं धेनूनामस्मि कामधुक्। प्रजनश्चास्मि कन्दर्पः सर्पाणामस्मि वासुकिः॥
Among weapons I am the thunderbolt; among cows I am Kamadhenu; among progenitors I am Kamadeva; among serpents I am Vasuki.
Connection: Among many, certain ones stand as exemplars — not the absolute best alone, but those of recognized rank. The kth largest is one of the elite k: the weakest among the strongest. The min-heap maintains this elite group by continuously expelling anyone who falls below the threshold of greatness. The heap's minimum (its weakest link) defines the boundary of excellence — the kth largest.