Return the k largest numbers in descending order using a min-heap in O(n log k). Compare against sorting and test edge cases in Python.
The problem
Return the k largest values of nums, largest first.
If k is larger than the list, return the whole list sorted descending.
Examples
Example 1
Input
top_k([10, 4, 8, 20, 15, 3, 25], 3)
Expected output
[25, 20, 15]
Example 2
Input
top_k([1, 2, 3], 1)
Expected output
[3]
+ 3 hidden tests on Submit — duplicates, k > len, k = 0.
Edge cases to ask about
- k = 0
- k larger than the list
- Duplicates in the top k
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Sort descending, slice | O(n log n) | O(n) | Simple and often fine — but it orders all n values to keep k. |
| Min-heap of size k | O(n log k) | O(k) | The heap's smallest is the k-th largest so far; replace it when something bigger arrives. |
| bestQuickselect | O(n) average | O(1) | Partition around a pivot until the k-th position is fixed (output then needs sorting). |
Walkthrough of the optimal approach (try it yourself first)
Keep a min-heap of the k largest values seen so far. Its root is the smallest of them, which is exactly the one to evict when a bigger value arrives. Each step costs O(log k), so the whole pass is O(n log k) with O(k) memory — much better than sorting when k is small and n is huge (or a stream).
heapq.nlargest(k, nums) does exactly this. Name it, then show you can write it.
Complexity: O(n log k) time, O(k) space. Each of the n elements may trigger a heap push or replace, which costs log k because the heap never holds more than k items.
Reveal the reference solution
import heapq def top_k(nums, k): heap = [] for x in nums: if len(heap) < k: heapq.heappush(heap, x) elif heap and x > heap[0]: heapq.heapreplace(heap, x) return sorted(heap, reverse=True)
The brute force, for comparison
def top_k(nums, k): return sorted(nums, reverse=True)[:k]
Follow-ups interviewers ask
- The data is a stream that never ends.
- Top k most FREQUENT elements.
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Top K Largest Elements in Python?
The optimal solution runs in O(n log k) time and O(k) auxiliary space. Each of the n elements may trigger a heap push or replace, which costs log k because the heap never holds more than k items.
What is the brute-force approach, and how do you optimise it?
Sort descending, slice: O(n log n) time, O(n) space. Simple and often fine — but it orders all n values to keep k. Min-heap of size k: O(n log k) time, O(k) space. The heap's smallest is the k-th largest so far; replace it when something bigger arrives. Quickselect: O(n) average time, O(1) space. Partition around a pivot until the k-th position is fixed (output then needs sorting).
What follow-up questions do interviewers ask about Top K Largest Elements?
The data is a stream that never ends. Top k most FREQUENT elements.