703. Kth Largest Element in a Stream☆

function topKFrequent(nums: number[], k: number): number[] {
  // 1) Count every value in one pass.
  const freq = new Map<number, number>();
  for (const n of nums) {
    freq.set(n, (freq.get(n) ?? 0) + 1);
  }

  // 2) Bucket sort: buckets[c] = all values seen exactly c times.
  //    A value's count is at most nums.length, so we need that many slots.
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [val, count] of freq) {
    buckets[count].push(val);
  }

  // 3) Walk buckets from the highest count down, collecting k values.
  const res: number[] = [];
  for (let c = buckets.length - 1; c >= 1 && res.length < k; c--) {
    for (const val of buckets[c]) {
      res.push(val);
      if (res.length === k) return res;
    }
  }
  return res;
}

function findKthLargest(nums: number[], k: number): number {
  // Min-heap of size k — the root is always the kth largest seen so far.
  const heap: number[] = [];

  function push(val: number): void {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[p] > heap[i]) { [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; }
      else break;
    }
  }

  function pop(): number {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < heap.length && heap[l] < heap[s]) s = l;
        if (r < heap.length && heap[r] < heap[s]) s = r;
        if (s === i) break;
        [heap[i], heap[s]] = [heap[s], heap[i]]; i = s;
      }
    }
    return top;
  }

  for (const n of nums) {
    push(n);                          // add every element
    if (heap.length > k) pop();       // evict the minimum when over-full
  }
  return heap[0];                     // root = kth largest
}

class KthLargest {
  private heap: number[] = [];
  private k: number;

  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const n of nums) this.add(n);
  }

  add(val: number): number {
    this._heapPush(val);
    if (this.heap.length > this.k) this._heapPop();
    return this.heap[0];   // min of the k-heap = kth largest overall
  }

  // --- min-heap helpers ---
  private _heapPush(val: number): void {
    this.heap.push(val);
    let i = this.heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  private _heapPop(): number {
    const top = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let smallest = i;
        if (l < this.heap.length && this.heap[l] < this.heap[smallest]) smallest = l;
        if (r < this.heap.length && this.heap[r] < this.heap[smallest]) smallest = r;
        if (smallest === i) break;
        [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
        i = smallest;
      }
    }
    return top;
  }
}

class Twitter {
  private static ts = 0;                      // global monotonic timestamp
  private tweets = new Map<number, { tweetId: number; time: number }[]>();
  private following = new Map<number, Set<number>>();

  postTweet(userId: number, tweetId: number): void {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId)!.push({ tweetId, time: Twitter.ts++ });
  }

  getNewsFeed(userId: number): number[] {
    // Collect latest tweet from every followee (plus self)
    const peers = new Set([userId, ...(this.following.get(userId) ?? [])]);
    // Min-heap keyed by time (max-10 merge via a max-heap simulation)
    // We use a simple sorted merge of per-user pointers for clarity.
    type Cursor = { list: { tweetId: number; time: number }[]; idx: number };
    const cursors: Cursor[] = [];
    for (const uid of peers) {
      const list = this.tweets.get(uid) ?? [];
      if (list.length > 0) cursors.push({ list, idx: list.length - 1 });
    }

    const result: number[] = [];
    while (result.length < 10 && cursors.length > 0) {
      // pick the cursor with the largest time (max-heap by time)
      let best = 0;
      for (let i = 1; i < cursors.length; i++) {
        if (cursors[i].list[cursors[i].idx].time >
            cursors[best].list[cursors[best].idx].time) {
          best = i;
        }
      }
      const cur = cursors[best];
      result.push(cur.list[cur.idx].tweetId);
      if (cur.idx === 0) {
        cursors.splice(best, 1);   // exhausted this user's list
      } else {
        cur.idx--;
      }
    }
    return result;
  }

  follow(followerId: number, followeeId: number): void {
    if (!this.following.has(followerId)) this.following.set(followerId, new Set());
    this.following.get(followerId)!.add(followeeId);
  }

  unfollow(followerId: number, followeeId: number): void {
    this.following.get(followerId)?.delete(followeeId);
  }
}