347 Top K Frequent Elements

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

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

Approach

There are three parts to this approach:

1. We set up a map to add counts of each entry in the input array. Map to count occurrences in array
2. We loop over the map and add entries to our bucket at position of the count that equals the number Set to keep track of values
3. We then add those into our results array, if length is equal k we break and return result

Solution

var topKFrequent = function(nums, k) {
	const freqMap = new Map();
	const bucket = [];
	const result = [];
	
	for (let num of nums) {
		freqMap.set(num, (freqMap.get(num) || 0) + 1);
	}
	
	for (let [num, freq] of freqMap) {
		bucket[freq] = (bucket[freq] || new Set()).add(num);
	}
	
	for (let i = bucket.length-1; i >= 0; i--) {
		if(bucket[i]) result.push(...bucket[i]);
		if(result.length === k) break;
	}
	
	return result;
};

topKFrequent([1,1,1,2,2,2,3,3,4,4,4],3)

Gotcha

• Using a Map makes it easy and concise to keep track of the counts.
• Using a Set is not there to ensure uniqueness, that is more or less handled by the Map, it is there to have an easy way to keep track
• The second loop will create a Set at bucket[freq]
• The first if-statement in the last for-loop is there to not break our loop as there could be undefined entries in our bucket in between numbers

References

LC

Related

DSA MOC
Set to keep track of values
Map to count occurrences in array
Map in JavaScript
Set in JavaScript