Kth Largest Element in an Array

Problem Given an integer array and an integer k, find the kth largest element — the kth largest in sorted order, not the kth distinct value.

Input / Output

• Input: integer array nums, integer k.
• Output: the kth largest element.

Constraints

• 1 <= k <= nums.length <= 10^5.
• Values may repeat; duplicates count separately.
• Values may be negative.

Example

• Input: nums = [3,2,1,5,6,4], k = 2 -> Output: 5
• Tricky case: nums = [3,2,3,1,2,4,5,5,6], k = 4 -> Output: 4. Note it is not 5 — duplicates each occupy a rank, which is the distinction most wrong answers miss.