Top K Frequent Words

Tagged: Priority Queue, Heap, Hash Table, String, Sorting, Trie

Problem

Given an array of strings, our task is to find Top K Frequent Words. The frequency must be in descending order. If the frequency is the same, then it must be ordered lexicographically.
For example,

Input: arr = ["everyday", "love", "coding", "i", "i", "love"], k = 2
Output: ["i", "love"]
Explanation: Both "i" and "love" have the same frequency. "i" comes before "love" because "i" is alphabetically lower than "love"

Input: arr = ["day", "sunny", "is", "the", "the", "the", "the", "sunny", "is", "is"], k = 4
Output: ["the", "is", "sunny", "day"]
Explanation: "the", "is", "sunny", "day" respectively has frequency 4, 3, 2, 1.

Solution

Kotlin
Java

fun topKFrequent(words: Array<String>, k: Int): List<String> {
    val map = mutableMapOf<String, Int>()
    words.forEach {
        map[it] = map.getOrDefault(it, 0) + 1
    }

    val priorityQueue = PriorityQueue(
        compareByDescending<Pair<Int, String>> { it.first }.thenBy { it.second }
    )
    map.forEach {
        priorityQueue.add(Pair(it.value, it.key))
    }

    val result = mutableListOf<String>()
    while (priorityQueue.isNotEmpty() && result.size < k) {
        val pair = priorityQueue.poll()
        result.add(pair.second)
    }

    return result
}

class FreqWord {
    private int frequency;
    private String word;

    public FreqWord(int frequency, String word) {
        this.frequency = frequency;
        this.word = word;
    }
}

class FreqWordComparator implements Comparator<FreqWord> {
    @Override
    public int compare(FreqWord freqWord1, FreqWord freqWord2) {
        if (freqWord1.frequency != freqWord2.frequency)
            return freqWord2.frequency - freqWord1.frequency;

        return freqWord1.word.compareTo(freqWord2.word);
    }
}

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> map = new HashMap<>();
    for (String word : words) {
        map.put(word, map.getOrDefault(word, 0) + 1);
    }

    PriorityQueue<FreqWord> priorityQueue = new PriorityQueue<>(new FreqWordComparator());
    map.forEach((key, value) -> {
                priorityQueue.add(new FreqWord(value, key));
            }
    );

    List<String> result = new ArrayList<>();
    while (!priorityQueue.isEmpty() && result.size() < k) {
        FreqWord freqWord = priorityQueue.poll();
        result.add(freqWord.word);
    }

    return result;
}

Top K Frequent Words

Problem#

Solution#

Problem

Solution