Kth Largest Element

Find the kth largest value in an unsorted array.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Kth Largest Element: A size-k min-heap retains the k largest values seen, so its root is the kth largest.

Input and goalFind the `k`th largest value in an unsorted array.

Seed the candidate heapFor nums = [3,2,1,5,6,4] and k = 2, push 3. The heap has room, so nothing is removed.

heap

• 3

input[3,2,1,5,6,4]current3processed1 of 6size1 <= k

Recognize it

Use it when an unsorted or streaming input asks for the kth largest item or the largest k items, while sorting every value would retain more order than the answer needs.

Keep true

After each input is pushed and any size-(k+1) overflow root is popped, the heap contains exactly the largest min(k, processed) values seen; its root is the weakest retained candidate.

Reuse it

For a bounded best-k set, choose the opposite heap polarity: a min-heap protects the largest k and a max-heap protects the smallest k; the root is always the next item to evict.

Pattern: Min-heap of size k.

Simple idea: Keep only the largest k values seen. The smallest value in that group is the kth largest overall.

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
   if not 1 <= k <= len(nums):
      raise ValueError("k must name an item in nums")

   heap: list[int] = []
   for num in nums:
      heapq.heappush(heap, num)
      if len(heap) > k:
         heapq.heappop(heap)
   return heap[0]

Cost: $O(n\log k)$ time and $O(k)$ space.