Kth Largest Element in an Array

Problem

Given an unsorted integer array and an integer k, return the kth largest element (not the kth distinct element).

Example

nums = [3,2,1,5,6,4], k = 2
Output: 5

Constraints

• 1 ≤ k ≤ nums.length ≤ 10^5

Approaches (discuss trade-offs)

1. Sort — O(n log n) time, O(1) space
2. Min-heap of size k — O(n log k) time, O(k) space
3. Quickselect — O(n) average, O(n²) worst case

Adobe follow-up

If the array is too large to fit in memory and arrives as a stream, which approach is optimal? What if k changes with each query?