LeetCode - 347. Top K Frequent Elements

Thoughts:

I choose hash map and bucket sort to solve this problem. Hash map for storing the key (number) and value (frequency). Bucket sort for sorting an array that the index is count, and the value is an array of the numbers with same count. The time complexity will be O(n).

Thoughts visuzlization:

nums = [1,1,1,2,2,3], k = 2

map: {1: 3, 2: 2, 3: 1}

freqs: [[], [3], [2], [1], [], [], []]
        0    1    2    3   4   5   6
index for representing the the count of frequency,
so the length of freqs is the length of nums plus 1 (1 is for 0 frequency)

answer: [1,2]
order doesn't matter in this problem

why is the time complexity O(n) ?

image that...
nums: [1,2,3,4,5]
freqs: [[], [1,2,3,4,5], [], [], [], []]
if the numbers are all different,
the time complexity will be O(n+n) -> O(n)
ps. if k = 2, then this case won't be qualified in this problem,
because the problem says that the answer is unique,
this will have  C⁵₂ = 10 combinations for answer

nums: [1,1,1,1,1]
freqs: [[], [], [], [], [1], []]
if the numbers are all the same,
the time complexity will be O(n+1) -> O(n)

the relationship between the array and the nested array is addition,
not multiplication

Code:

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const map = new Map();
  const freqs = Array.from({ length: nums.length + 1 }, () => []);
  const answer = [];
  for (let num of nums) {
    map.set(num, (map.get(num) || 0) + 1);
  }
  for (let [key, count] of map) {
    freqs[count].push(key);
  }
  for (let i = freqs.length - 1; i > 0; i--) {
    if (freqs[i].length === 0) continue;
    for (let num of freqs[i]) {
      if (answer.length < k) {
        answer.push(num);
      }
    }
  }
  return answer;
};

Reference

Original link

Bucket sort intro video