Kth Largest Element in an Array

You are given an integer array nums and an integer k. Return the k-th largest value that would appear if the array were sorted in descending order.

Important details to keep in mind:

• You are looking for the k-th largest element in sorted order, not the k-th distinct value — duplicate numbers each count as their own position in that ordering.
• k is guaranteed to be a valid index into the (conceptually) sorted array, so you never need to handle an out-of-range request.
• You should aim for a solution that avoids a full sort of the array whenever possible, though the primary goal is producing the correct value.

Examples

Example 1:

Input: nums = [7, 2, 9, 4, 1], k = 2

Output: 7

Explanation:

Sorted in descending order the array becomes [9, 7, 4, 2, 1]. The 2nd largest entry is 7.

Example 2:

Input: nums = [5, 5, 5, 3, 8, 5], k = 4

Output: 5

Explanation:

Sorted in descending order: [8, 5, 5, 5, 5, 3]. Counting duplicates individually, the 4th position holds 5 (the third occurrence of 5 in this descending list).

Example 3:

Input: nums = [-1, -3, -2], k = 1

Output: -1

Explanation:

Sorted in descending order: [-1, -2, -3]. The largest value, and thus the 1st largest, is -1.

Constraints

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