Find the k-th largest element in an array
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array `nums` and an integer `k`, return the **k-th largest** element in the array.
Notes:
- The k-th largest element is the element that would appear in position `k` (1-indexed) if the array were sorted in **descending** order.
- Do **not** fully sort the array unless you want to (but consider performance).
## Input
- `nums`: array of integers
- `k`: integer (`1 <= k <= len(nums)`)
## Output
- The k-th largest integer.
## Constraints
- `1 <= len(nums) <= 2 * 10^5`
- `-10^9 <= nums[i] <= 10^9`
Quick Answer: This question evaluates proficiency with selection algorithms, array manipulation, and analysis of time and space complexity, reflecting competency in order-statistics and basic data structures.
Given an integer array `nums` and an integer `k`, return the **k-th largest** element in the array.
The k-th largest element is the element that would appear in position `k` (1-indexed) if the array were sorted in **descending** order. Note this is the k-th largest element in sorted order, not the k-th distinct element (duplicates count).
You are not required to fully sort the array — a heap of size `k` (O(n log k)) or Quickselect (O(n) average) both work and are preferred for large inputs.
### Input
- `nums`: array of integers
- `k`: integer (`1 <= k <= len(nums)`)
### Output
- The k-th largest integer.
### Example 1
```
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
```
Descending order is `[6, 5, 4, 3, 2, 1]`; the 2nd element is `5`.
### Example 2
```
Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
```
Descending order is `[6, 5, 5, 4, 3, 3, 2, 2, 1]`; the 4th element is `4` (duplicates count).
Constraints
- 1 <= len(nums) <= 2 * 10^5
- -10^9 <= nums[i] <= 10^9
- 1 <= k <= len(nums)
Examples
Input: ([3, 2, 1, 5, 6, 4], 2)
Expected Output: 5
Explanation: Descending: [6,5,4,3,2,1]; the 2nd largest is 5.
Input: ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)
Expected Output: 4
Explanation: Descending: [6,5,5,4,3,3,2,2,1]; the 4th element is 4 (duplicates count toward rank).
Hints
- You don't need to fully sort the array. To find the k-th largest, you only need to track the k largest elements seen so far.
- A min-heap of size k works well: push elements and pop the smallest whenever the heap exceeds size k. After processing all elements, the heap root is the k-th largest. This is O(n log k).
- For optimal average performance, use Quickselect (partition-based selection) to find the element at index (n - k) in ascending order, giving O(n) average time.
- Watch the indexing: the k-th LARGEST in descending order equals the element at 0-based index (n - k) when sorted ascending. Duplicates count toward the rank.