Kth Largest Element in an Array
Problem Description
Given an integer array nums and integer k, return the kth largest element. Note: kth largest, not kth distinct element.
Example 1:
Input: nums=[3,2,1,5,6,4], k=2
Output: 5
Example 2:
Input: nums=[3,2,3,1,2,4,5,5,6], k=4
Output: 4
DE Shaw Tier 2 — LC 215.
Three approaches:
1. Min-heap of size k: O(n log k) time, O(k) space. Evict smallest when heap exceeds k.
2. Quickselect: O(n) average, O(n^2) worst. Partition like quicksort.
3. Sort: O(n log n) — mention but don't use.
For streaming data, mention heap approach is the only viable one.
Example Test Cases
Example 1
Input: [[3,2,1,5,6,4],2]
Expected: 5
Example 2
Input: [[3,2,3,1,2,4,5,5,6],4]
Expected: 4
Example 3
Input: [[1],1]
Expected: 1
Run your code to see the results