Kth Largest Integer

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

Note that it is the kth largest element in sorted order, not the kth distinct element — duplicates count individually.

Solve it in better than O(n log n) time on average (i.e., don't just sort the whole array).

Example 1

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

Example 2

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

Constraints

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