Skip to content

Kth Largest Element in an Array

LeetCode

01 · Question

Given an integer array nums and an integer k, return the kth largest element in the array.

Assume 1 <= k <= len(nums); duplicate values occupy separate ranks.

02 · Analysis

Keep a min-heap of at most k values. After inserting a value, discard the smallest if necessary; the heap retains the largest k values of the processed prefix. Its root is the kth largest, counting duplicate occurrences separately. Require 1 <= k <= len(nums). Time O(n log(k+1)), auxiliary space O(k).

03 · Solution

Reference solution

1import heapq
2

3def findKthLargest(nums: List[int], k: int) -> int:
4    heap = []
5    for x in nums:
6        heapq.heappush(heap, x)
7        if len(heap) > k:
8            heapq.heappop(heap)
9    return heap[0]
Next
Top K Frequent Elements