Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Function signature

func FindKthLargest(nums []int, k int) int

Examples

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Explanation: Sorted: [1,2,3,4,5,6]. The 2nd largest is 5.

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Explanation: Sorted: [1,2,2,3,3,4,5,5,6]. The 4th largest is 4.

Example 3:

Input: nums = [1], k = 1
Output: 1

Example 4:

Input: nums = [7,7,7,7], k = 2
Output: 7
Explanation: All elements are the same. 2nd largest is also 7.

Constraints

• 1 <= k <= len(nums) <= 10000
• -10000 <= nums[i] <= 10000

Hints

1. You could sort and return nums[len(nums)-k]. What's the time complexity?
2. A min-heap of size k can solve this in O(n log k). Why min-heap for kth largest?
3. The smallest element in a heap of the k largest elements is the kth largest.

Notes

• Multiple approaches work: sort O(n log n), heap O(n log k), or quickselect O(n) average.
• The heap approach is particularly useful for streaming data.