Kth Largest Element in an Array
Find the kth largest element using sorting vs a min-heap of size k.
Kth Largest Element in an Array
Problem: Given an array of numbers and an integer k, find the kth largest element. Not the kth distinct — just the kth largest when sorted.
Example:
- Input:
nums = [3, 2, 1, 5, 6, 4],k = 2 - Output:
5(sorted descending:[6, 5, 4, 3, 2, 1], the 2nd is5)
Note
Think about it this way: you want the top k largest numbers. The kth largest is just the smallest of those top k.
Brute Force
View Brute Force
Optimal — Min Heap of Size k
View Optimal Solution
| Approach | Time | Space | When to use |
|---|---|---|---|
| Sort | O(n log n) | O(1) | Small arrays, simple situations |
| Min Heap | O(n log k) | O(k) | Large arrays, especially when k is small |