The problem
Find the k-th largest number in an unsorted list (k-th in sorted order, not the k-th distinct).
Input: [3, 2, 1, 5, 6, 4], k = 2 Output: 5
Picture it
Picture a podium with only k places, where the weakest of the k sits at the front. Every number tries to get on; if the podium is over-full, the weakest steps off. After everyone has tried, the weakest person still standing is exactly the k-th largest.
How to recognise it
- You need one element by rank (the k-th largest) from an unsorted array.
- You do not need the full sorted order, only the value sitting at one position of it.
- "k-th" counts duplicates: in
[3, 2, 3, 1, 2, 4, 5, 5, 6]with k = 4 the answer is 4, because the sorted order from the top is 6, 5, 5, 4. - n can reach 10^5, so repeated linear scans are out, and a hint like "can you do it without sorting?" points to a heap (a tree stored in a list that keeps its smallest item at index 0, with O(log n) push and pop) or to quickselect (a partial quicksort).
Start with brute force
Find the maximum and remove it, k − 1 times. The maximum of what is left is the answer.
def find_kth_largest_brute(nums, k):
s = list(nums)
for _ in range(k - 1):
s.remove(max(s)) # scan to find it, scan again to remove it
return max(s)
Each round scans the list twice, so time is O(n · k) and space is O(n) for the copy. For n = 10^5 and k = 5 × 10^4 that is about 5 × 10^9 steps, too slow. Sorting the whole array (O(n log n)) would pass the limits, but it orders far more than the question needs.
From brute force to the idea
- Find the waste. The brute force re-examines the entire list in every round, even though the same big numbers keep winning.
- Only the top k matter. The k-th largest is decided by the k largest numbers, and it is the smallest of them.
- Keep those k in a min-heap. Push each number. If the heap grows past k items,
heappopremoves its smallest, which cannot be among the top k. - Read the front. After the last number, the heap holds exactly the k largest, and
heap[0]is the smallest of them: the k-th largest.
This is the key idea: a min-heap that never grows beyond k items, with the answer at its front.
Quickselect can reach O(n) on average, but its worst case is O(n²) and it rearranges the input, so the heap is the safer first answer.
The key idea
Min-heap of size k: the top is the answer. O(n log k).
Python solution
def find_kth_largest(nums, k):
heap = [] # min-heap of the k largest so far
for x in nums:
heappush(heap, x)
if len(heap) > k:
heappop(heap) # the weakest leaves
return heap[0]LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (remove the max k − 1 times) | O(n · k): two scans of the list per round | O(n): the copy |
| Min-heap of size k (shown code) | O(n log k): each number does one push and at most one pop on a heap of at most k + 1 items | O(k): the heap |
Edge cases
- k = 1: the heap keeps one number, the maximum.
- k = n: nothing is popped, and the front is the minimum.
- Duplicates (
[3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4): returns 4, because equal values count separately. - All equal (
[-1, -1], k = 2): returns -1. - Single element (
[5], k = 1): returns 5. - k larger than n: not allowed by the problem. The code does not raise an error;
find_kth_largest([1, 2], 3)returns 1, which is not a real 3rd largest. - Empty array:
heap[0]raisesIndexError. - Input is not changed. The code needs
from heapq import heappush, heappop.
Common mistakes
- Using a max-heap of all n numbers and popping k times. It works but costs O(n + k log n) time and O(n) space.
- Counting distinct values by mistake. The problem asks for the k-th in sorted order, so duplicates stay.
- Popping before pushing when the heap is full, which replaces the smallest even when the new number is smaller. On
[4, 3, 2, 1]with k = 2 that returns 1 instead of 3. - Returning
heap[k - 1]: a heap is not sorted, so only index 0 has a guaranteed meaning.
Return the sum of the k largest numbers in the array. Describe your approach, then write it if you like.
Compare with our answer
The same min-heap of size k now holds exactly the numbers you want. Instead of reading the front, add up the heap at the end.
from heapq import heappush, heappop
def sum_of_top_k(nums, k):
heap = []
for x in nums:
heappush(heap, x)
if len(heap) > k:
heappop(heap)
return sum(heap)
sum_of_top_k([3, 2, 1, 5, 6, 4], 2) is 11 (6 + 5). Time O(n log k) for the loop plus O(k) for the sum, space O(k).
A strong answer mentions: reusing the size-k min-heap, summing its contents (not just the front), and the O(n log k) cost.
1. You must report the 100 highest scores from a log of 50 million entries, and memory is tight. Which approach fits best?
The size-100 min-heap uses O(100) memory and O(n log 100) time. Sorting or heapifying everything needs all entries in memory, and 100 scans of the log cost 100 times as much work for no gain.
2. Why does a min-heap, not a max-heap, give the k-th largest in the shown solution?
The top k numbers are kept, and the one at rank k is the least of them, which a min-heap exposes at index 0. A max-heap is possible with negated values, and a heap is only partly ordered, not sorted.
3. A learner pops first when the heap is full, then pushes (if len(heap) >= k: heappop(heap) before heappush). Which input now gives a wrong answer?
With pop-then-push the newest number always replaces the smallest, even when it is smaller. On [4, 3, 2, 1] the heap ends as [1, 4] and returns 1. Ascending input happens to work, equal values are harmless, and with k = n nothing is popped.
Score 60% or more and the lesson is marked complete.