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

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Examples

Example 1:

Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 2
Output: ["the","is"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

Constraints

  • 1 <= words.length <= 500
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • k is in the range [1, The number of unique words[i]]

Thinking Process

  1. Custom Comparator: The key is the two-level sorting: frequency first, then lexicographic order
  • Heap gives fast access to min/max without full sorting.
  • Size-k heap handles Top-K in O(n log k).
  • Lazy deletion when elements leave the heap before removal.
Binary heap 1 3 2 parent ≤ children (min-heap)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Min/max heap (this problem) O(n log k) O(k) Top-K, streaming median
Two heaps O(n log n) O(n) Median from data stream
Heap + lazy deletion O(n log n) O(n) Delayed removal
Priority-driven search O(n log n) O(n) Dijkstra, best-first expansion

Solution

Solution: Hash Map + Custom Sorting

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> cnt;
        for(auto& word: words) {
            cnt[word]++;
        }
        vector<string> rtn;
        for(auto& [key, value]: cnt) {
            rtn.emplace_back(key);
        }
        sort(rtn.begin(), rtn.end(), [&](const string& a, const string& b){
            return cnt[a] == cnt[b]? a < b : cnt[a] > cnt[b];
        });
        rtn.erase(rtn.begin() + k, rtn.end());
        return rtn;
    }
};

Solution Explanation

Approach: Min/max heap (this problem)

Key idea: 1. Custom Comparator: The key is the two-level sorting: frequency first, then lexicographic order

How the code works:

  1. Custom Comparator: The key is the two-level sorting: frequency first, then lexicographic order
    • Heap gives fast access to min/max without full sorting.
    • Size-k heap handles Top-K in O(n log k).
    • Lazy deletion when elements leave the heap before removal.

Walkthrough — input words = ["i","love","leetcode","i","love","coding"], k = 2, expected output ["i","love"]:

“i” and “love” are the two most frequent words. Note that “i” comes before “love” due to a lower alphabetical order.

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Custom Comparator: The key is the two-level sorting: frequency first, then lexicographic order
  2. Hash Map Efficiency: unordered_map provides O(1) average case for frequency counting
  3. Sorting Trade-off: Simple sorting works well for small inputs; heap is better for large k
  4. Lexicographic Order: When frequencies are equal, use standard string comparison (<)

References

Template Reference