Heaps / Priority Queues/Practice/Kth Largest Element in Array

Kth Largest Element - Heap Solution Explained

mediumTime: O(n log k)Space: O(k)

Keep a min-heap holding the k largest elements seen so far. Walk the array: push each element, and if the heap grows past k, pop the smallest. When you finish, the top of the heap is the kth largest.

Why it works

The min-heap always evicts the least useful element - anything smaller than k survivors cannot matter. The heap never exceeds k entries, so each push/pop is O(log k) and the whole pass is O(n log k) with O(k) space, beating a full sort’s O(n log n).

The problem

Given an integer array nums and an integer k, return the kth largest element. Note that it is the kth largest in sorted order, not the kth distinct element.

Hints

  • Sorting is O(n log n). Can you do O(n log k)?
  • Maintain a min-heap of exactly k elements.
  • If a new element is larger than the heap's minimum, replace it.
  • The heap minimum at the end is the kth largest.

Test cases

InputExpected
find_kth_largest([3,2,1,5,6,4], 2)5
find_kth_largest([3,2,3,1,2,4,5,5,6], 4)4

Reference starter code

import heapq

def find_kth_largest(nums, k):
    # Use a min-heap of size k
    pass

print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5
print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))  # 4

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.

Studying Heaps / Priority Queues but not ready to grind? Get the 30-day plan by email.
One email with the study plan. No spam, unsubscribe anytime.