$$ \newcommand\Tr{\mathrm{Tr}} \newcommand{\braket}[2]{\langle #1 \mid #2 \rangle} \newcommand\I{\mathbb{I}} \newcommand{\avg}[1]{\left< #1 \right>} \newcommand{\RD}{D} \newcommand{\ri}{\mathrm{i}} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\Sign}{Sign} \newcommand{\ii}{\mathrm i} \newcommand{\vv}{\mathrm v} \newcommand{\ff}{\mathrm f} \newcommand{\mm}{\mathrm m} \newcommand{\ee}{\mathrm e} \newcommand{\xx}{\mathrm x} \newcommand{\RR}{\mathrm R} \newcommand{\dd}{\mathrm d} \newcommand{\FF}{\mathrm F} \newcommand{\BB}{\mathrm B} \newcommand{\vph}{v_{\mathrm{ph}}} $$

Top K Frequent Words

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

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;
}