347. Top K Frequent Elements

In this tutorial we will solve 347. Top K Frequent Elements from leetcode.

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 347. Top K Frequent Elements

Problem statement

In this problem we have an input array of integers nums and an integer value k. We have to return k most frequent numbers from the array.

Example from leetcode.

Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:
Input: nums = [1], k = 1
Output: [1]

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

In example 1, number 1 appears 3 times, number 2 appears 2 times and number 3 appears 1 time. Since we are asked to return k=2 frequent numbers hence we will return number 1 and 2.

Approach

To solve this problem we will use a hash map to save the number of times a given integer appears in the input array nums. We can then sort the frequency and select the top k elements.

Let's solve the input nums = [1,1,1,2,2,3], k = 2.

freq = {}

strs  = [1, 1, 1, 2, 2, 3]
         ^
1 is not in the hashmap, add new entry.
freq = {
  1: 1
}


strs  = [1, 1, 1, 2, 2, 3]
            ^
1 is in the hashmap, update entry.
freq = {
  1: 2
}


strs  = [1, 1, 1, 2, 2, 3]
               ^
1 is in the hashmap, update entry.
freq = {
  1: 3
}


strs  = [1, 1, 1, 2, 2, 3]
                  ^
2 is not in the hashmap, add new entry.
freq = {
  1: 3,
  2: 1
}


strs  = [1, 1, 1, 2, 2, 3]
                     ^
2 is in the hashmap, update entry.
freq = {
  1: 3,
  2: 2
}


strs  = [1, 1, 1, 2, 2, 3]
                        ^
3 is not in the hashmap, add new entry.
freq = {
  1: 3,
  2: 2,
  3: 1
}

Now, we will sort the frequency hash map based on the number of times each integer has appeared in the nums array. And we will sort in any order and accordingly pick the k elements. However, in this example I will sort the elements in descending order and pick the first k elements.

sort the hash map

sort(freq)
= {
  1: 3,
  2: 2,
  3: 1
}


Now, pick first 2 (as k=2) elements

[1, 2]

Code

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  let freq = new Map();
  for (let n of nums) {
    freq.set(n, (freq.get(n) || 0) + 1);
  }
  const sortedFreq = Array.from(freq.entries()).sort((a,b) => b[1] - a[1]);
  let result = [];
  for(let i = 0; i < k; i++) {
    result.push(sortedFreq[i][0]);
  }
  return result;
};

Complexity

Time complexity: O(nlogn)

In order to create the frequency hash map we have to traverse the array n times. Therefore, the time complexity of first array is O(n).

The frequency hash map will have m key-value pairs, so time complexity to sort m key-value pairs will be O(mlogm). However, in worst case m will be equal to n. So, worst time complexity will be O(nlogn).

Finally, we have to log k times to get the k top elements. So, time complexity of this operation will be O(k).

In total, the time complexity will be O(n + mlogm + k). Which in worst case would be O(nlogn).

Space complexity: O(n)

Our hash map will save m key-value pairs. So, space complexity will be O(m).

Sorted array will hold m elements so, space complexity will be O(m).

Result array will hold k elements so, space complexity will be O(k).

In worst case, m will be equal to n. So, the worst space complexity O(m + m + k) will be O(n).