Given an array of integers arr and an integer k, return the k most frequent elements.

1-top-k-frequent-elements.js

import MinHeap from "./min_heap.js";

export function topKFrequent(arr, k) {
  // create map where we store numbers from arr as keys,
  // and their frequencies in arr as values
  const map = {};

  // fill up frequency map
  for (let i = 0; i < arr.length; ++i) {
    const char = arr[i];
    map[char] = (map[char] ?? 0) + 1;
  }

  // grab an array of unique numbers from the frequency map
  const keys = Object.keys(map);

  // we are going to store numbers from arr along with their frequencies
  // in a min heap
  const heap = new MinHeap();

  for (let i = 0; i < keys.length; ++i) {
    const char = parseInt(keys[i]);
    const freq = map[char];
    if (heap.size() < k) {
      // if heap size is less than k,
      // we just add a number with it's frequency to the heap
      heap.offer([freq, char]);
    } else if (freq > heap.peek()[0]) {
      // if heap is of size k, we first check our current number and it's frequency
      // against the top of the heap (which is the least frequent number since so far)
      // if current number frequency is greater, we remove the top of the heap,
      // and insert the current one instead
      // otherwise the current one is less frequent and we dont need it in the heap
      heap.poll();
      heap.offer([freq, char]);
    }
  }

  // at this point we have a heap of size k,
  // which is exactly the k most frequent numbers from the arr

  const result = [];
  while (heap.size() > 0) {
    result.push(heap.poll()[1]);
  }

  return result;
}

2-README.md