Problem

In a Meta-style ranking pipeline, you may need the kth largest score from an unsorted list without fully sorting it. Given an integer array nums and an integer k, return the kth largest element in the array.

The kth largest element is the value that would appear at position k in a descending sort, counting duplicates as separate elements.

Formal Specification

• Input:
  • nums: a list of integers
  • k: an integer where 1 <= k <= len(nums)
• Output:
  • An integer representing the kth largest element in nums

Examples

Example 1

• Input: nums = [3, 2, 1, 5, 6, 4], k = 2
• Output: 5
• Explanation: In descending order, the array is [6, 5, 4, 3, 2, 1], so the 2nd largest element is 5.

Example 2

• Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
• Output: 4
• Explanation: In descending order, the array is [6, 5, 5, 4, 3, 3, 2, 2, 1], so the 4th largest element is 4.

Constraints

• 1 <= len(nums) <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= len(nums)
• Duplicates may appear in the array