Intermediate LevelData Structures & Algorithms
How do you find the Kth Largest Element in an array efficiently?
❓ Interview Prompt: Compare Min-Heap O(N log K), Quickselect O(N) average, and sorting O(N log N) approaches for Kth Largest element.
Approach 1: Sort — $O(N \log N)$
Sort descending; return index K−1. Too slow when called frequently.
Approach 2: Min-Heap of size K — $O(N \log K)$
Maintain a heap of the K largest seen. Pop the minimum when size exceeds K. Root = Kth largest.
Approach 3: QuickSelect — $O(N)$ average, $O(N^2)$ worst
Partial Quick Sort: partition around a pivot; only recurse into the partition containing index N−K. Randomised pivot gives $O(N)$ expected.
Code Implementation Example
typescript
// QuickSelect — O(N) average
function findKthLargest(nums: number[], k: number): number {
const target = nums.length - k; // k-th largest = (n-k)-th smallest
function quickSelect(lo: number, hi: number): number {
const pivot = nums[hi];
let p = lo;
for (let i = lo; i < hi; i++) {
if (nums[i] <= pivot) [nums[p++], nums[i]] = [nums[i], nums[p - 1]]; // fixed
}
[nums[p], nums[hi]] = [nums[hi], nums[p]];
if (p === target) return nums[p];
return p < target ? quickSelect(p + 1, hi) : quickSelect(lo, p - 1);
}
return quickSelect(0, nums.length - 1);
}💡QuickSelect O(N) average for Kth Largest — partial partitioning.
🎯 Interview Key Takeaway
QuickSelect is O(N) average for Kth element. Min-Heap O(N log K) is better for streaming data. Know both — interviewers test all three approaches.
#DSA#QuickSelect#Heap#Sorting#Intermediate
Back to all Data Structures & Algorithms Questions→