Top K Frequent Words

Problem

Given an array of strings words and an integer k, return the k most frequent words, sorted by frequency from highest to lowest. Words with the same frequency are ordered lexicographically (alphabetically).

Constraints

• 1 ≤ words.length ≤ 500
• 1 ≤ words[i].length ≤ 10
• lowercase English
• k is valid

Approach — Heaps / Top-K

This is a Heaps / Top-K problem. The idea: use a heap so the min, max, or top-k element stays reachable in O(log n) per operation. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log k) time.

Solution code

Python

class Solution:
    def topKFrequent(self, words, k):
        from collections import Counter
        c = Counter(words)
        return sorted(c, key=lambda w: (-c[w], w))[:k]

Java

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> count = new HashMap<>();
        for (String w : words) count.merge(w, 1, Integer::sum);

        // Size-k MIN-heap: the head is the "most evictable" word —
        // lowest frequency, or on a frequency tie the lexicographically
        // LARGER word (because ties should keep the alphabetically smaller).
        PriorityQueue<String> heap = new PriorityQueue<>((a, b) ->
            count.get(a).equals(count.get(b))
                ? b.compareTo(a)                 // tie: larger word -> head -> evicted
                : count.get(a) - count.get(b));  // else: smaller count -> head -> evicted
        for (String w : count.keySet()) {
            heap.offer(w);
            if (heap.size() > k) heap.poll();    // keep only the best k -> O(N log k)
        }

        // Heap holds the k answers worst-first; reverse them into order.
        LinkedList<String> res = new LinkedList<>();
        while (!heap.isEmpty()) res.addFirst(heap.poll());
        return res;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.