Kth Largest Element in an Array
Part of Practice: Top-K Fundamentals
Given an unsorted array of integers and an integer k, return the k-th largest element — the element that would sit in the k-th position if the array were sorted in descending order. Duplicates count as separate positions, so the 2nd largest of [5, 5, 3] is 5.
The array can hold up to 10^5 values ranging from -10^4 to 10^4, and 1 ≤ k ≤ n. The interview follow-up is always the same: can you do it without fully sorting the array?
Examples
- Input:
- nums = [3, 2, 1, 5, 6, 4], k = 2
- Output:
- 5
Sorted descending: [6, 5, 4, 3, 2, 1]. The 2nd element is 5.
- Input:
- nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
- Output:
- 4
Sorted descending: [6, 5, 5, 4, 3, 3, 2, 2, 1]. The 4th element is 4 — the duplicate 5s each take a position.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.