692. Top K Frequent Words

Top K Frequent Words

Problem Description

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

 

Example 1:

Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]

Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]

Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

 

Constraints:

• 1 <= words.length <= 500
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• k is in the range [1, The number of unique words[i]]

 

Follow-up: Could you solve it in O(n log(k)) time and O(n) extra space?

Approach) Bucket Sort

• Use a HashMap to store each number and its frequency.
• Use bucket array to save numbers into different buckets whose index is the frequency

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const freqMap = new Map();
    const bucket = [];
    const output = []
    
    for(let num of nums) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }
    
    for(let [num, freq] of freqMap) {
        if(bucket[freq] === undefined) bucket[freq] = [num];
        else bucket[freq].push(num);
    }
    
    for(let i = bucket.length-1; i >= 0; i--) {
        if(bucket[i] === undefined) continue;
        output.push(...bucket[i].sort())
        if(output.length >= k) return output.slice(0, k)
    }
};

Complexity 

Time Complexity

The time complexity will be O(n + nlogn).

Space Complexity

The space complexity should also be O(1).

Approach) Hashtable / Hashmap and Set

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
   var topKFrequent = function(words, k) {
    let map=new Map()
    let res=[]
    for(let i of words){
        if(map.has(i)){
            map.set(i,map.get(i)+1)
        }else{
            map.set(i,1)
        }
    }
    
    res=[...map.keys()].sort((a,b)=>{
        if(map.get(a)===map.get(b)){
            return b < a ? 1:-1
        }
        return map.get(b)-map.get(a)
    }).slice(0,k)
    
    return res
};

1. Map all the words count in the array
2. Then sort there keys
3. If keys count match then compare there value

Note: return b < a ? 1:-1

• b will store your current value
• if b comes before a then it sorted forward else sorted backward
• sort() reference

Approach) Hashtable / Hashmap and Sort

var topKFrequent = function(words, k) {
    words = words.sort()
    let map = {}
    for(word of words){
        if(map[word]) map[word]++
        else map[word] = 1
    }
    return Object.entries(map).sort((a, b) => {
            return b[1] - a[1]
    }).slice(0, k).map(a => a[0])
};

Approach) Heap (Priority Queue)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */
var topKFrequent = function(words, k) {
    // use a max heap (priority queue)
    // remove k from heap after finishing the heap and add to an array
    
    //find the number of occurances by using object
    const occurances = {};
    words.forEach((word) => {
        if (occurances[word]) {
            occurances[word] = occurances[word] + 1;
        } else {
            occurances[word] = 1;
        }
    })
    
    // declare new priority queue
    const maxHeap = new MaxPriorityQueue({ compare: (a, b) => {
        if (a.rank > b.rank) return -1; // do not swap
        if (a.rank < b.rank) return 1; // swap
        const { word: wordA } = a;
        const { word: wordB } = b;
        return wordA.localeCompare(wordB);
    }});
    // add all items to the priority queue
    for (const word in occurances) {
        maxHeap.enqueue({ word, rank: occurances[word]})
    }
    // take off k elements add to result
    const result = [];
    for (let i = 0; i < k; i += 1) {
        const { word } = maxHeap.dequeue();
        result.push(word);
    }
    return result;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #692. Top K Frequent Words

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!