Pattern Guide
Top-K & Streaming Algorithms
"Maintain top-K elements in streams. Heap-based selection, frequency tracking."
Top-K streaming problems maintain a running set of K most frequent or largest elements as data arrives. Core tool: min-heap of size K — evict smallest when size exceeds K. Variations: top-K frequent elements (bucket sort trick for O(n)), K closest points, find median in stream (two heaps), sliding window maximum (monotonic deque). Key: choose between sort O(n log n), heap O(n log k), or bucket sort O(n) based on constraints.
Problems you can solve with this pattern
5 problems · click any to start solving
// Top K frequent elements — O(n) with bucket sort
function topKFrequent(nums, k) {
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
// Bucket sort: index = frequency
const bucket = Array.from({length: nums.length + 1}, () => []);
for (const [num, f] of freq) bucket[f].push(num);
const result = [];
for (let i = bucket.length - 1; i >= 0 && result.length < k; i--)
result.push(...bucket[i]);
return result.slice(0, k);
}
// Find median from data stream — two heaps
class MedianFinder {
constructor() {
// lo = max-heap (lower half), hi = min-heap (upper half)
this.lo = []; // simulate max-heap by negating
this.hi = []; // min-heap
}
addNum(num) {
// Push to lo, then balance
this._pushMax(this.lo, num);
this._pushMin(this.hi, this._popMax(this.lo)); // move max of lo to hi
if (this.hi.length > this.lo.length)
this._pushMax(this.lo, this._popMin(this.hi));
}
findMedian() {
if (this.lo.length > this.hi.length) return -this.lo[0];
return (-this.lo[0] + this.hi[0]) / 2;
}
// Heap helpers (arrays sorted manually here — in practice use a heap library)
_pushMax(h, v) { h.push(-v); h.sort((a,b)=>a-b); }
_popMax(h) { return -h.shift(); }
_pushMin(h, v) { h.push(v); h.sort((a,b)=>a-b); }
_popMin(h) { return h.shift(); }
}Top-K elements via min-heap of size K: push each element; if size > K, pop minimum. Result = heap contents. O(n log k). Top-K frequent: count frequencies, then heap on (freq, element). Trick: bucket sort by frequency for O(n) — bucket[freq] = list of elements with that frequency. Find median in stream: two heaps (max-heap for lower half, min-heap for upper half), maintain size balance.
// Top K frequent elements — O(n) with bucket sort
function topKFrequent(nums, k) {
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
// Bucket sort: index = frequency
const bucket = Array.from({length: nums.length + 1}, () => []);
for (const [num, f] of freq) bucket[f].push(num);
const result = [];
for (let i = bucket.length - 1; i >= 0 && result.length < k; i--)
result.push(...bucket[i]);
return result.slice(0, k);
}
// Find median from data stream — two heaps
class MedianFinder {
constructor() {
// lo = max-heap (lower half), hi = min-heap (upper half)
this.lo = []; // simulate max-heap by negating
this.hi = []; // min-heap
}
addNum(num) {
// Push to lo, then balance
this._pushMax(this.lo, num);
this._pushMin(this.hi, this._popMax(this.lo)); // move max of lo to hi
if (this.hi.length > this.lo.length)
this._pushMax(this.lo, this._popMin(this.hi));
}
findMedian() {
if (this.lo.length > this.hi.length) return -this.lo[0];
return (-this.lo[0] + this.hi[0]) / 2;
}
// Heap helpers (arrays sorted manually here — in practice use a heap library)
_pushMax(h, v) { h.push(-v); h.sort((a,b)=>a-b); }
_popMax(h) { return -h.shift(); }
_pushMin(h, v) { h.push(v); h.sort((a,b)=>a-b); }
_popMin(h) { return h.shift(); }
}- Sort all: O(n log n) — simple, fine for most
- Min-heap size K: O(n log k) — better when k << n
- Bucket/counting sort: O(n) — when values bounded (frequencies 1..n)
- QuickSelect: O(n) average — find kth largest without sorting
Two-heap median trick: lo (max-heap) holds lower half, hi (min-heap) holds upper half. Maintain |lo.size - hi.size| ≤ 1. Both tops give the median. Each addNum is O(log n).
Sliding window max: Use monotonic deque (see monotonic-queue chapter) not heap — O(n) vs O(n log k).