Kth Smallest Element
Mahabharata — The Ranking Test — Finding the kth Least Powerful Warrior
k-वां लघुतम — भारी-ढेर रखो k तत्वों का। शीर्षे सबसे बड़ा — वही k-वां लघुतम॥
*kth smallest — keep a max-heap of k elements. At the top stands the largest among k smallest — that is the kth smallest.*
The Story
Find the kth smallest element in an unsorted array.
For `arr=[7,10,4,3,20,15]`, k=3: answer=7. (Sorted: 3,4,7,10,15,20 → 3rd smallest = 7)
**Max-Heap of size k:** - Maintain a max-heap of the k smallest elements seen so far - For each element: add to heap - If heap size > k: remove the maximum (it's too large to be in top-k smallest) - After processing all: heap.top() = kth smallest
```java PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a); // Max-heap for (int x : arr) { pq.offer(x); if (pq.size() > k) pq.poll(); // Remove largest } return pq.peek(); ```
Why max-heap (not min-heap)? - We maintain exactly k elements — the k SMALLEST seen so far - When a new element arrives and the heap is full: compare with the LARGEST in the heap - If new element < heap.top(): replace the top (the new element is smaller than the previous kth smallest → it belongs) - If new element >= heap.top(): ignore (it's at least as large as the current kth smallest → doesn't belong) - The MAXIMUM of the k smallest elements is the kth smallest element!
Trace `[7,10,4,3,20,15]`, k=3: - Add 7,10,4 → heap=[10,7,4] - Add 3: heap=[10,7,4,3], size=4>3 → poll max=10 → heap=[7,4,3] - Add 20: heap=[20,7,4,3]? size=4>3 → poll=20 → heap=[7,4,3] - Add 15: heap=[15,7,4,3]? size=4>3 → poll=15 → heap=[7,4,3] - Return heap.peek()=7 ✓
The Sort-and-Index Approach
Sort the array and return arr[k-1]. O(n log n).
public static int kthSmallestBruteForce(int[] arr, int k) {
Arrays.sort(arr);
return arr[k-1];
}The Max-Heap-of-K-Smallest Wisdom
public static int kthSmallest(int[] arr, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // Max-heap
for (int x : arr) {
pq.offer(x);
if (pq.size() > k) pq.poll();
}
return pq.peek();
}Step-by-Step Walkthrough
[1], k=1 Add 1: [1]. size=1≤1. Return 1 ✅
Deep Insight
**Max-heap for k-smallest vs Min-heap for k-largest:** - k-smallest: MAX-heap of size k. Top = kth smallest. New element replaces top if smaller. - k-largest: MIN-heap of size k. Top = kth largest. New element replaces top if larger.
**Mnemonic:** "Opposite heap" — to find k-smallest, use max-heap (keep track of the boundary with the largest of the small elements).
**Also solvable with Quickselect:** O(n) average, O(n²) worst case. For guaranteed O(n log k), use heap.
**hp-1 vs hp-2:** Almost identical. hp-1 (kth smallest) uses MAX-heap. hp-2 (kth largest) uses MIN-heap.
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 smallest → MAX-heap of size k ✅ kth largest → MIN-heap of size k ✅ Opposite heap type from what you'd expect ✅ heap.peek() is the boundary — the kth value **LeetCode Trigger Phrases:** → "kth smallest element" → Maintain k smallest/largest seen so far → Heap boundary pattern
Bhagavad Gita 15.17
उत्तमः पुरुषस्त्वन्यः परमात्मेत्युदाहृतः। यो लोकत्रयमाविश्य बिभर्त्यव्यय ईश्वरः॥
But beyond these two is the Supreme Person — the Imperishable Lord who permeates and sustains all three worlds.
Connection: Among the field of n warriors, the kth smallest occupies a specific rank — not the best, not the worst, but a precise position in the ordering. The max-heap acts as a discriminating filter: it keeps the k most qualified (smallest), and the one standing at the top of this special heap — the boundary guardian — is the answer. Like the Gita's three levels (perishable, imperishable, Supreme), the heap maintains three zones: below-k, the kth element (heap.top), and above-k.