Kth Largest Element 20 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

Find the kth largest element in an unsorted array. Note: kth largest, not kth distinct.

nums = [3, 2, 1, 5, 6, 4], k = 2
# Sorted: [1, 2, 3, 4, 5, 6]
# 2nd largest = 5

nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
# Sorted: [1, 2, 2, 3, 3, 4, 5, 5, 6]
# 4th largest = 4

Three approaches:

Sort: O(n log n) — sort and return nums[-k]. Simple but not optimal.
Min-heap of size k: O(n log k) — maintain k largest elements in a min-heap. Top of heap = kth largest.
QuickSelect: O(n) average — partition like quicksort but only recurse on one side

The min-heap approach: keep a heap of size k. If a new element is larger than the heap's min, pop the min and push the new one. The heap's min is always the kth largest.

📋 Instructions

Implement `find_kth_largest(nums, k)` using a min-heap of size k. Test with both examples.

Push first k elements. Then for each remaining element, if it's > heap[0], heappop and heappush the new element. At the end, heap[0] is the kth largest.

🧪 Test Cases

Input

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

Expected

5

Test case 1

Input

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

Expected

4

Test case 2

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›