Top K Frequent Words

Find the k most frequent words in the array.

Top K Frequent Words

Problem Statement

You get an array of strings called words. You also get a number k.

Your task is simple:

• Find the k most frequent words in the array.
• Sort the words from the highest frequency to the lowest frequency.
• If two words have the same frequency, sort them in alphabetical order (A to Z).

Constraints

• The array words has between 1 and 500 items.
• Each word has between 1 and 10 letters.
• All letters in each word are lowercase (a to z).
• k is between 1 and the total number of unique words.

Solution Idea

We solve this problem in three simple steps:

• Step 1: Count each word. We use a Map to store how many times each word appears in the array.
• Step 2: Use a Min Heap. A min heap always keeps the smallest value on top. We add each word and its frequency into the heap.
• Step 3: Keep only k words. If the heap size becomes bigger than k, we remove the smallest one. This way, only the top k frequent words stay in the heap.

At the end, we take all words out of the heap and reverse the order. This gives us the words from highest frequency to lowest frequency.

Code

var topKFrequent = function(words, k) {
    const map = new Map();
    const minHeap = new NewMinHeap();
    let result = [];

    // Step 1: Count frequency of each word
    for (let word of words) {
        map.set(word, (map.get(word) ?? 0) + 1);
    }

    // Step 2: Add word and frequency to min heap
    for (let [word, freq] of map) {
        minHeap.offer([freq, word]);

        // Step 3: Remove smallest if heap size is more than k
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }

    // Take all words out of heap
    while (minHeap.size() > 0) {
        result.push(minHeap.poll()[1]);
    }

    // Reverse to get highest frequency first
    return result.reverse();
};

Why This Method Works

• The Map helps us count words quickly.
• The min heap only keeps the top k frequent words at any time.
• When we pop from the heap, the smallest frequency comes out first. So we reverse the result at the end to get the correct order (highest to lowest).

Time Complexity

• Counting words takes O(n) time, where n is the number of words.
• Adding and removing from the heap takes O(log k) time for each unique word.
• So the total time is about O(n log k).