The Pirate’s Hunt

You are a pirate who has discovered a chest full of gold coins. Each coin has a value, represented as an integer in the array coins.

Your mission is to find the kᵗʰ most valuable coin — the one that ranks k from the top in value.

Note: We are looking for the kᵗʰ largest coin by value, not necessarily a unique value.

Can you find it without sorting all the coins?

Example 1

Input:

coins = [3, 2, 1, 5, 6, 4], k = 2

Output:

def find_kth_treasure(coins, k) -> 5

Explanation:

The sorted treasure values are [6, 5, 4, 3, 2, 1]. The 2nd largest coin has value 5.

Example 2

Input:

coins = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4

Output:

def find_kth_treasure(coins, k) -> 4

Explanation:

Sorted values are [6, 5, 5, 4, 3, 3, 2, 2, 1]. The 4th largest coin is 4.

Constraints

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