Kth Highest Bid

medium

An auction house just closed bidding on a rare anvil. You have the full list of bids (unsorted, duplicates allowed) and the floor manager wants to know the k-th highest bid — counting duplicates, not the k-th distinct value.

Return that bid. Sorting the whole list works, but the manager handles millions of bids; can you do better than sorting everything when k is small?

Example 1

in bids = [3, 2, 1, 5, 6, 4], k = 2

out 5

Sorted descending: 6, 5, 4, ... — the 2nd highest is 5.

Example 2

in bids = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4

out 4

Descending: 6, 5, 5, 4, ... — duplicates count.

Constraints

· 1 <= k <= len(bids) <= 2000
· -10^4 <= bids[i] <= 10^4