Top k frequent elements
StopHeap
- CH1 heap
16/16
Count first, then keep the k most frequent as (count, value) pairs.
Step through it →Heap / Priority Queue
A heap keeps its smallest item on top, and a push or pop only repairs one path from the top to a leaf, so each costs O(log n).
Kth largest: keep the k largest in a min-heap
StopHeap
numsk
- CH1 heap
The heap starts empty. It will keep the 2 largest numbers seen so far.
Typical cost O(log n) per push/pop; O(n log k) for top-kFull lesson: Kth Largest Element in an Array →
When to reach for it
- You need the k largest or smallest, not everything sorted.
- You keep taking the smallest or earliest item while new ones arrive.
- You need an answer after every item of a stream, like a running median.
- Sorting everything works, but costs O(n log n) when k is small.
What stays true
A push adds at the end and swaps up past larger parents. A pop moves the last item into the root's place and settles it along one path. Either way, only one path from the root to a leaf changes.
Every parent is at most its children
StopHeap
InvariantEvery parent is at most its children, so the root is the smallest.✓ Holds
- CH1 heap
The heap starts empty. It will keep the 4 largest numbers seen so far.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
Equal numbers count separately: the 4th largest is 4. Skipping repeats would give 3.
Kth largest on the inputs that trip it up
StopHeap
- CH1 heap
The heap starts empty. It will keep the 4 largest numbers seen so far.
Answer4Steps25
Variants
Find median from data stream
StopHeap
- CH1 low
- CH2 high
14/14
Two heaps hold the smaller and the larger half. The median sits at their tops.
Step through it →Meeting rooms II
StopHeap
- CH1 heap
27/27
Keep the end times of meetings in progress on a heap. The earliest end says whether a room is free.
Step through it →The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Kth largest: keep the k largest in a min-heap
StopHeap
- CH1 heap
The heap starts empty. It will keep the 2 largest numbers seen so far.
kth_largest.py
import heapqdef find_kth_largest(nums, k): if k > len(nums): return None heap = [] for x in nums: heapq.heappush(heap, x) if len(heap) > k: heapq.heappop(heap) return heap[0]