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

java class Solution { public List<String> topKFrequent(String[] words, int k) { Map<String, Integer> freq = new HashMap<>(); for (String w : words) freq.put(w, freq.getOrDefault(w, 0) + 1); PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> { int fa = freq.get(a), fb = freq.get(b); if (fa != fb) return Integer.compare(fa, fb); return b.compareTo(a); }); for (String w : freq.keySet()) { pq.offer(w); if (pq.size() > k) pq.poll(); } List<String> result = new ArrayList<>(); while (!pq.isEmpty()) result.add(pq.poll()); Collections.reverse(result); return result; } }

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