This problem can be solved using either the Heap (Priority Queue) approach, which has a time complexity of O(N log k), or the Sorting approach, which has a time complexity of O(N log N).

We can return the answer in any order, so a better approach is to use Quickselect. It has an average time complexity of O(N) and a worst-case complexity of O(N2), although the probability of encountering the worst-case scenario is negligible.

Top K frequent function

Let’s go through the solution step-by-step.

var topKFrequent = function(nums, k) {
    const arr = freqArrOf(nums);
    
    quickSelect(arr, k);

    const res = [];
    for (let i = 0; i < k; i++) {
        res.push(arr[i].val);
    }
    return res;
}

First, we create an array of items where each element contains the number and its frequency. For example, for the input [1, 1, 1, 2, 2, 3], the resulting array will be [{val: 1, freq: 3}, {val: 2, freq: 2}, {val: 3, freq: 1}].

Then we use Quickselect to move the top k frequent elements to the beginning of the array.

Finally, we extract the values of the first k elements as an array and return it.

Quickselect

Here’s the quickselect function:

var quickSelect = function(arr, k) {
    let lo = 0;
    let hi = arr.length - 1;
    let len = 0;
    while (len !== k) {
        len = partition(arr, lo, hi) + 1;
        if (len < k) lo = len;
        else if (len > k) hi = len - 1;
    }
}

The goal of Quickselect is to move the top k frequent elements to the beginning of the array. To achieve this, we use a function called partition. Each time we call this function, it returns a random index where elements before that index (inclusive) have higher frequencies than the elements after it. We repeat this process until we obtain an index equal to k-1, which means all elements before index k have higher frequencies.

When we obtain an index:

  1. If index < k-1, it means all elements before this index have higher frequencies. There is no need to repartition them, so next time we only partition elements after this index.
  2. If index > k-1, it means all elements after this index have lower frequencies. There is no need to repartition them, so next time we only partition elements before this index.
  3. If index == k-1, we can stop partitioning.

Partition

var partition = function(arr, lo, hi) {
    const pivot = lo + Math.round(Math.random() * (hi - lo));
    const pivotFreq = arr[pivot].freq;
    while (lo < hi) {
        if (arr[lo].freq < pivotFreq) {
            swap(arr, lo, hi);
            hi--;
        } else {
            lo++;
        }
    }
    if (arr[lo].freq < pivotFreq) lo--;
    return lo;
}

In the partition function, we select a random element as the pivot within the given range (lo - hi). We move elements such that all elements bigger than or equal to the pivot are placed at the beginning of the array.

After this operation, elements before index lo will be greater than or equal to the pivot, indicating that elements before index lo (inclusive) have higher values than the elements after index lo.

We select a random index as the pivot to decrease the probability of encountering the worst-case scenario of O(N2).

Code

Here is the complete code:

var topKFrequent = function(nums, k) {
    const arr = freqArrOf(nums);
    
    quickSelect(arr, k);

    const res = [];
    for (let i = 0; i < k; i++) {
        res.push(arr[i].val);
    }
    return res;
}

var freqArrOf = function(nums) {
    const arr = [];
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (!map.has(nums[i])) {
            const val = {val: nums[i], freq: 0};
            map.set(nums[i], val);
            arr.push(val);
        }
        map.get(nums[i]).freq++;
    }
    return arr;
}

var quickSelect = function(arr, k) {
    let lo = 0;
    let hi = arr.length - 1;
    let len = 0;
    while (len !== k) {
        len = partition(arr, lo, hi) + 1;
        if (len < k) lo = len;
        else if (len > k) hi = len - 1;
    }
}

var partition = function(arr, lo, hi) {
    const pivot = lo + Math.round(Math.random() * (hi - lo));
    const pivotFreq = arr[pivot].freq;
    while (lo < hi) {
        if (arr[lo].freq < pivotFreq) {
            swap(arr, lo, hi);
            hi--;
        } else {
            lo++;
        }
    }
    if (arr[lo].freq < pivotFreq) lo--;
    return lo;
}

var swap = function(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}