Kth Largest Element in an Array (Min-Heap)

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

Note that it is the k-th largest element in the sorted order, not the k-th distinct element.

Can you solve it without sorting in O(n log k) or O(n) average time?

Example 1

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Constraints

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4