Q20: Kth Largest Element in an Array
Find the $k$-th largest element in an unsorted array using QuickSelect partitioning algorithm or Min-Heap.
QuickSelect Partition Algorithm
function findKthLargest(nums, k) {
const targetIndex = nums.length - k;
function quickSelect(left, right) {
const pivot = nums[right];
let p = left;
for (let i = left; i < right; i++) {
if (nums[i] <= pivot) {
[nums[i], nums[p]] = [nums[p], nums[i]];
p++;
}
}
[nums[p], nums[right]] = [nums[right], nums[p]];
if (p === targetIndex) return nums[p];
if (p < targetIndex) return quickSelect(p + 1, right);
return quickSelect(left, p - 1);
}
return quickSelect(0, nums.length - 1);
}
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5💡 Partitions array around pivot. If pivot index equals target position (length - k), returns target value; otherwise selectively recurses into the target partition half.
Key Takeaways
- QuickSelect provides average O(n) time complexity.
- Avoids full array sorting which takes O(n log n).
Knowledge Check
What is the average time complexity of QuickSelect?