AI Hints
Home›DSA in Python Tutorial›More Practice: Heaps, Search and DP
DSA in Python · Lesson 118 of 132

Practice: Kth Largest Element

A heap of size k.

⏱ 2 min read▶ Video at 2:20:45🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Find the K th largest number in a list. For example, the third largest. Sorting works, but it's O of N log N, and sorts far more than we need. Pause. Which structure keeps track of the biggest few numbers?

Practice: Kth Largest Element
From the video: Practice: Kth Largest Element
  • The kth largest number
  • Sorting does too much
  • Which structure helps?

A min heap of size k

We keep a min heap holding the K largest numbers seen so far. Each new number is pushed in, and if the heap grows past K, we pop the smallest. So the top of the heap is always the K th largest. Run it. The third largest is eight.

kth_largest.pypython
import heapq

def kth_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

print(kth_largest([3, 9, 1, 8, 4, 10, 2, 7], 3))
Output
8

Costs

Each push and pop costs O of log K, so the whole thing is O of N log K. When K is small, that's much faster than sorting. It also works on a stream of numbers that never ends, because we only ever keep K of them. Python's heap Q dot N largest uses this same idea.

keyvalue
Heap sizek
Each stepO(log k)
TotalO(n log k)
Shortcutheapq.nlargest(k, nums)

Summary

Keep a min heap of the K largest numbers, and its top is the answer. Next, binary search on a rotated list.

Key takeaways
  • Min heap of size k
  • Pop when too big
  • Top is the answer
Next up: Practice: Search a Rotated Array — binary search with a twist