Kth Largest Element in an Array

Problem: Given an integer array and an integer k, find the kth largest element in the array (the kth largest in sorted order, not the kth distinct element).

Constraints: 1 <= k <= array length <= 10^5.

Example: nums = [3,2,1,5,6,4], k = 2 -> 5.

Approach: Brute force: sort descending and index k-1, O(n log n). Optimized: use a min-heap of size k, pushing each element and popping when size exceeds k — the heap root ends up being the kth largest, O(n log k). Further optimized: Quickselect (partition-based) gives average O(n) time.