Kth Largest Element in an Array
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return the k-th largest element of an unsorted array (counting duplicates).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Do you need all elements sorted, or only the k best?
- Hint 2Keep the k largest in a min-heap; its top is the smallest of the k, which is the k-th largest.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A talent show where only the top 3 scorers stay on the podium. The weakest person on the podium stands at the edge. When a new contestant arrives, compare with only that weakest person: if the newcomer scores higher, the weakest steps down and the newcomer steps up. At the end, the person at the edge is exactly 3rd best.
- The obvious way
Sort descending and take position k: O(n log n).
- The key insight
Keep a min-heap holding the best k numbers seen. For each new number, push it; if the heap grows beyond k, pop the smallest. After all numbers, the heap's top is the k-th largest. Time O(n log k).
- The algorithm
- Start with an empty min-heap.
- Push each number.
- If the heap has more than k numbers, pop the smallest.
- The top of the heap is the answer.
Watch it run
Examplenums = [3, 2, 1, 5, 6, 4], k = 2
3 and 2 come in: the podium (size 2) is {2, 3}. The edge person is 2.
heap: 2, 3
Where people slip
- Use a MIN-heap for the k-th largest (and a max-heap for the k-th smallest).
- Quickselect gives O(n) on average but the heap is simpler and safer in interviews.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
import heapq
def find_kth_largest(nums, k):
podium = [] # min-heap of the k best so far
for number in nums:
heapq.heappush(podium, number)
if len(podium) > k:
heapq.heappop(podium) # the weakest steps down
return podium[0] # the person at the edge = k-th bestNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.