Problem statement

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

Sort the answer by frequency from highest to lowest; words with the same frequency are ordered lexicographically.

Example 1

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

Example 2

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

Example 3

Input: words = ["a"], k = 1
Output: ["a"]

Constraints

• 1 <= words.length <= 40
• 1 <= words[i].length <= 8
• words[i] consists of lowercase English letters.
• 1 <= k <= number of distinct words

Hints for Top K Frequent Words

1. Hint 1

   Count the words, then sort the distinct ones by (frequency descending, word ascending).

2. Hint 2

   The tie-break is lexicographic on the word itself, not on insertion order.

3. Hint 3

   A heap of size k with the same comparator gives O(n log k).

How to solve Top K Frequent Words

Count words, sort the distinct ones by (frequency descending, word ascending), and take the first k.

Approach

1. Count with a map.
2. Sort keys by (-count, word).
3. Return the first k.

Why it works

The composite key implements exactly the required order; a heap of size k with the same comparator gives O(n log k).

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• The tie-break is lexicographic on the word, not insertion order.

Reference solution

Python

def topKFrequent(words, k: int):
    count = {}
    for w in words:
        count[w] = count.get(w, 0) + 1
    ordered = sorted(count.keys(), key=lambda w: (-count[w], w))
    return ordered[:k]

Java

public static String[] topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap<>();
    for (String w : words) count.put(w, count.getOrDefault(w, 0) + 1);
    List<String> unique = new ArrayList<>(count.keySet());
    Collections.sort(unique, (a, b) -> {
        int ca = count.get(a), cb = count.get(b);
        if (ca != cb) return cb - ca;
        return a.compareTo(b);
    });
    return unique.subList(0, k).toArray(new String[0]);
}

C++

vector<string> topKFrequent(vector<string>& words, int k) {
    unordered_map<string, int> count;
    for (const string& w : words) count[w]++;
    vector<string> unique;
    for (const auto& kv : count) unique.push_back(kv.first);
    sort(unique.begin(), unique.end(), [&](const string& a, const string& b) {
        int ca = count[a], cb = count[b];
        if (ca != cb) return ca > cb;
        return a < b;
    });
    unique.resize(k);
    return unique;
}

JavaScript

var topKFrequent = function(words, k) {
    const count = new Map();
    for (let i = 0; i < words.length; i++) {
        count.set(words[i], (count.get(words[i]) || 0) + 1);
    }
    const unique = [];
    count.forEach(function(_, w) { unique.push(w); });
    unique.sort(function(a, b) {
        const ca = count.get(a), cb = count.get(b);
        if (ca !== cb) return cb - ca;
        if (a < b) return -1;
        if (a > b) return 1;
        return 0;
    });
    return unique.slice(0, k);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium