Find kth largest element in array
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
Given an unsorted array of integers `nums` and an integer `k`, return the **k-th largest** element in the array.
The 1st largest element is the maximum element, the 2nd largest is the second highest, and so on. Equivalently, the k-th largest element is the value that would appear at index `k - 1` if the array were sorted in **descending** order.
**Requirements:**
1. Handle duplicates correctly. Duplicates count as separate positions, e.g. `nums = [5, 5, 4]`, `k = 2` returns `5` (not `4`).
2. Describe your approach and analyze its time and space complexity. Try to design an algorithm that is more efficient than fully sorting the array. (You do not need to provide working code unless asked.)
**Input:**
- `nums`: an array of integers
- `k`: an integer where `1 <= k <= len(nums)`
**Output:**
- The k-th largest element (an integer).
**Constraints (typical interview scale):**
- `1 <= n <= 2 * 10^5`
- `-10^9 <= nums[i] <= 10^9`
**Example:**
- `nums = [3, 2, 1, 5, 6, 4]`, `k = 2` -> `5`
- `nums = [5, 5, 4]`, `k = 2` -> `5`
Quick Answer: A classic Meta software engineer onsite coding question: return the k-th largest element from an unsorted integer array, handling duplicates correctly. It tests order statistics and selection algorithms — sort, size-k min-heap (O(n log k)), and quickselect (O(n) average) — and the candidate's ability to beat a full sort.
Given an unsorted array of integers `nums` and an integer `k`, return the **k-th largest** element in the array.
The 1st largest element is the maximum, the 2nd largest is the second highest, and so on. Equivalently, the k-th largest element is the value at index `k - 1` if the array were sorted in **descending** order.
Duplicates count as separate positions. For example, `nums = [5, 5, 4]`, `k = 2` returns `5` (not `4`).
Try to design an algorithm more efficient than fully sorting the array.
**Input:**
- `nums`: an array of integers
- `k`: an integer where `1 <= k <= len(nums)`
**Output:**
- The k-th largest element (an integer).
**Example:**
- `nums = [3, 2, 1, 5, 6, 4]`, `k = 2` -> `5`
- `nums = [5, 5, 4]`, `k = 2` -> `5`
Constraints
- 1 <= n <= 2 * 10^5
- -10^9 <= nums[i] <= 10^9
- 1 <= k <= len(nums)
- Duplicates are counted as separate positions.
Examples
Input: ([3, 2, 1, 5, 6, 4], 2)
Expected Output: 5
Explanation: Sorted descending: [6,5,4,3,2,1]. The 2nd largest is 5.
Input: ([5, 5, 4], 2)
Expected Output: 5
Explanation: Duplicates count separately. Sorted descending: [5,5,4]. The 2nd largest is 5, not 4.
Hints
- You do not need the whole array sorted — you only need one order statistic.
- A min-heap of size k keeps exactly the k largest elements seen so far; its root is the k-th largest. This runs in O(n log k) and works even for streaming input.
- Quickselect (the partition step of quicksort, recursing into only one side) gives O(n) average time in place. Randomize the pivot to avoid the O(n^2) worst case.
- Duplicates need no special handling: compare by value and treat equal values as distinct positions. Sorting [5,5,4] descending gives [5,5,4], so the 2nd largest is 5.