Kth Largest Value
Problem
Given an unsorted list of numbers and a rank k, return the value that would sit in position k if the list were arranged from largest to smallest. Ranking is by value, so repeated values each occupy their own rank. You may assume k is at least 1 and never exceeds the length of the list.
Examples
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Why: ordered from the top the values run 6, 5, 4, 3, 2, 1Input: nums = [7, 7, 7], k = 2
Output: 7
Why: duplicates each take a rank of their ownInput: nums = [9], k = 1
Output: 9
Why: edge case, the only value is also the largestHints
0 / 3
Sorting the whole list answers the question but orders far more values than the rank actually requires.
Only the k largest values ever matter, and among those the one you want is the weakest. A structure that surrenders its smallest item cheaply fits that shape.
Keep a collection of at most k values whose smallest is always available. Add each value as you scan, and whenever the collection exceeds k, discard its smallest. When the scan ends, that smallest surviving value is the answer.
Solution
A min-heap capped at k entries keeps exactly the k largest values seen so far, and its root is the weakest of them, which is the k-th largest overall. Each value costs a push and possibly a pop, both logarithmic in k rather than in n. This beats full sorting whenever k is much smaller than the list. Time is O(n log k) and space is O(k).
import heapq
def kth_largest(nums, k):
heap = [] # a min-heap holding the k best values
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the weakest of the k + 1 candidates
return heap[0] # the smallest survivor is the k-th largest
print(kth_largest([3, 2, 1, 5, 6, 4], 2)) # -> 5
print(kth_largest([7, 7, 7], 2)) # -> 7
print(kth_largest([9], 1)) # -> 9Stuck on the idea rather than the code? Top K Elements covers it.