Top-K Streaming

// 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(); }
}