195. Kth Largest Element in an Array
You are given an integer array nums and an integer k. Return the k-th largest value in the array — the element that would sit in position k if nums were written out in decreasing order.
Duplicates keep their own slots: in [3, 3, 2] the 2nd largest is 3, not 2.
Sorting answers this immediately in O(n log n); the classic follow-up is to do better, since you never actually needed the full sorted order.
Example 1:
Input: nums = [5, 1, 4, 2, 8], k = 2
Output: 5
Explanation: In decreasing order the array reads [8, 5, 4, 2, 1]; the entry in position 2 is 5.
Example 2:
Input: nums = [2, 3, 3, 1], k = 3
Output: 2
Explanation: Duplicates count separately: decreasing order is [3, 3, 2, 1], so the 3rd largest is 2.
Constraints:
- 1 ≤ k ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
Hints:
Sorting in decreasing order and reading index k − 1 is already correct. Now ask: which part of that sort's work did you never need?
Only the top k values matter. Keep a min-heap of size k while scanning — evict the root whenever the heap grows past k — and the root at the end is the answer, in O(n log k).
Quickselect goes further: one partition pass tells you which side of the pivot holds the k-th largest, so you recurse into only that side, for O(n) average time.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [5, 1, 4, 2, 8], k = 2
Expected output: 5