Kth Largest Element in an Array (Heap Edition)

Find the kth largest element in an unsorted array using a heap-based approach.

heap priority-queue array selection

Implement a function `kth_largest(nums, k)` that returns the kth largest element in the given list `nums`. The kth largest element is determined after sorting the array in non-increasing order, and the element at the kth position (1-indexed) is the answer. You must use a heap-based approach (e.g., maintain a min-heap of size k). The function should handle duplicate values correctly. The input list will have at least one element, and k is guaranteed to be between 1 and len(nums) inclusive. Provide the function signature: `def kth_largest(nums: list, k: int) -> int:`.

Constraints

1 <= len(nums) <= 10^5
1 <= k <= len(nums)
Values in nums are integers within the range [-10^4, 10^4].

Example

>>> kth_largest([3,2,1,5,6,4], 2)
5
>>> kth_largest([3,2,3,1,2,4,5,5,6], 4)
4
>>> kth_largest([1], 1)
1
>>> kth_largest([-1, -2, -3], 1)
-1

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about maintaining a min-heap of size k. The top of that heap will be the kth largest.

You can use Python's `heapq` module to implement the heap operations.

Start by pushing the first k elements, then for each subsequent element, replace the root if the new element is larger.

The root after processing all elements will be your answer.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.