Given an unsorted array of integers and an integer k, find the kth largest element in the array. Note that it is the kth largest in sorted order, not the kth distinct element.
For example, given [3, 2, 1, 5, 6, 4] and k = 2, the answer is 5.
Explain your approach to solving this problem and state the time and space complexity.
How to approach it
- Hint 1
Think about what data structure efficiently tracks the smallest or largest elements as you scan the array.
- Hint 2
A min-heap of size k can help: the top of the heap is always the kth largest element seen so far.
- Hint 3
Iterate through the array, pushing each element onto the heap. If the heap size exceeds k, pop the smallest. At the end, the heap top is the answer.
Ready to answer it out loud?
Record your answer in 1:00 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.