Kth Largest Element in an Array

Given an array and an integer k, return the k-th largest element (not the k-th distinct one — duplicates count).

Example

Input: 3 2 1 5 6 4, k = 2 Output: 5

Approach

Keep a min-heap of size k containing the k largest values seen so far. For each new number, if it's bigger than the heap's smallest element (the root of a min-heap), swap it in. After processing everything, the heap's root is exactly the k-th largest — this runs in O(n log k), better than sorting the whole array (O(n log n)) when k is small.

Walkthrough

1import heapq
2heap = nums[:k]
3heapq.heapify(heap)
4for num in nums[k:]:
5    if num > heap[0]:
6        heapq.heapreplace(heap, num)
7print(heap[0])

Input format

Line 1: the array, space-separated Line 2: k

Print the k-th largest value.