# Top K Frequent Words
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/top-k-frequent-words)
Canonical: https://scaleengineer.com/dsa/problems/top-k-frequent-words
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Bucket Sort](https://scaleengineer.com/algorithms/bucket-sort)
**Data structures:** Array, Hash Table, String, Trie, Heap (Priority Queue)
**Companies:** [Intel](https://scaleengineer.com/companies/intel), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Yandex](https://scaleengineer.com/companies/yandex), [Yelp](https://scaleengineer.com/companies/yelp), [Netflix](https://scaleengineer.com/companies/netflix), [Pocket Gems](https://scaleengineer.com/companies/pocket-gems), [Attentive](https://scaleengineer.com/companies/attentive), [Smartsheet](https://scaleengineer.com/companies/smartsheet), [Robinhood](https://scaleengineer.com/companies/robinhood), [Box](https://scaleengineer.com/companies/box)
---
## Problem
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**.

**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 = 4
**Output:** ["the","is","sunny","day"]
**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]]`

**Follow-up:** Could you solve it in `O(n log(k))` time and `O(n)` extra space?

# Approaches
## Hash Map and Sorting
This approach first calculates the frequency of each word using a Hash Map. Then, it places all unique words into a list and sorts this list based on custom criteria: primarily by frequency in descending order, and secondarily by lexicographical order for words with the same frequency. Finally, it returns the first `k` elements of the sorted list.
**Time:** O(N*L + U log U * L), where `N` is the total number of words, `U` is the number of unique words, and `L` is the average word length. 
- `O(N * L)` to iterate through the words and build the frequency map.
- `O(U log U * L)` to sort the `U` unique words, as each comparison can take up to `O(L)` time. In the worst case where `U` is close to `N`, this simplifies to `O(N log N * L)`. · **Space:** O(U * L), where `U` is the number of unique words and `L` is the average length of a word. In the worst case, all words are unique (`U=N`), so the space complexity becomes `O(N * L)`. This space is used for the frequency map and the list of candidates.
**Pros:** The logic is easy to follow and implement using standard data structures and sorting functions.; It correctly solves the problem and is a good starting point.
**Cons:** The time complexity is dominated by the sorting step, which sorts all unique elements, not just the top k.; It is less efficient than heap-based solutions, especially when `k` is much smaller than the number of unique words `N`.
### Explanation
The most straightforward way to solve this problem is to first count how many times each word appears. A `HashMap` is a perfect tool for this, mapping each word to its frequency. Once we have the counts for all unique words, we can put these words into a list. The core of this method is to sort this list. We need a custom sorting logic: for any two words, we first look at their frequencies. The word with the higher frequency should come first. If their frequencies are identical, we then compare the words themselves alphabetically, with the lexicographically smaller word coming first. After applying this custom sort to the entire list of unique words, the top `k` elements of the list are our answer.
### Algorithm
- Create a `HashMap<String, Integer>` to store the frequency of each word in the input array.
- Iterate through the `words` array and populate the map. For each word, increment its corresponding count.
- Create a new `ArrayList<String>` containing all the unique words (the keys from the frequency map).
- Sort this list of unique words using a custom `Comparator`.
- The comparator should first compare words based on their frequencies (retrieved from the map) in descending order.
- If two words have the same frequency, the comparator should then sort them by their natural lexicographical (alphabetical) order in ascending order.
- After sorting, the list will be ordered according to the problem's requirements.
- Return the first `k` elements of the sorted list using `subList(0, k)`.

## Hash Map and Min-Heap
This is a more optimized approach that avoids sorting the entire set of unique words. It first calculates word frequencies using a Hash Map. Then, it uses a Min-Heap (implemented as a `PriorityQueue` in Java) of size `k` to efficiently keep track of the top `k` frequent words encountered so far. The heap's custom ordering ensures that the element with the lowest frequency (or lexicographically largest for ties) is always at the top, ready to be removed if a more frequent or lexicographically smaller word is found.
**Time:** O(N*L + U log k * L), where `N` is the total number of words, `U` is the number of unique words, `k` is the number of elements to return, and `L` is the average word length.
- `O(N * L)` to build the frequency map.
- `O(U log k * L)` to process the `U` unique words, with each heap operation taking `O(log k)` time and string comparisons taking `O(L)`.
- Since `U <= N`, the complexity is often simplified to `O(N log k)`. · **Space:** O(U * L), where `U` is the number of unique words and `L` is the average length of a word. The space is used for the frequency map (`O(U * L)`) and the heap (`O(k * L)`). In the worst case, `U=N`, so the space complexity is `O(N * L)`.
**Pros:** Significantly more efficient than the sorting approach, with a time complexity of `O(N log k)`.; This is a classic and highly effective pattern for any "Top K" style problem.; It avoids the overhead of sorting the entire collection of items.
**Cons:** The comparator logic for the min-heap is more complex than a standard sort comparator.; An extra step is required to reverse the elements from the heap to get the final sorted output.
### Explanation
This approach improves upon the sorting method by not sorting all the unique words. After counting frequencies with a `HashMap`, we use a Min-Heap. A Min-Heap is a data structure that always keeps the smallest element at the top. We can cleverly define what "smallest" means to solve our problem. We want to keep the `k` words with the *highest* frequency. So, we configure the heap to consider words with *lower* frequency as "smaller". If frequencies are tied, we consider the lexicographically *larger* word as "smaller".

We iterate through our unique words and add them to the heap. Whenever the heap size exceeds `k`, we remove the top element, which is guaranteed to be the "smallest" (least frequent, or lexicographically largest on tie) among all words currently in the heap. By the end, the heap contains exactly the top `k` frequent words. The final step is to extract them from the heap and put them in the correct order (highest frequency first), which requires reversing the order they come out of the min-heap.

```java
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> count = new HashMap<>();
        for (String word : words) {
            count.put(word, count.getOrDefault(word, 0) + 1);
        }

        PriorityQueue<String> heap = new PriorityQueue<>(
            (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
            w2.compareTo(w1) : count.get(w1) - count.get(w2) 
        );

        for (String word : count.keySet()) {
            heap.offer(word);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        List<String> result = new ArrayList<>();
        while (!heap.isEmpty()) {
            result.add(heap.poll());
        }
        Collections.reverse(result);
        return result;
    }
}
```
### Algorithm
- Build a `HashMap<String, Integer>` to store the frequency of each word, just like in the sorting approach.
- Create a `PriorityQueue<String>` (Min-Heap) of a maximum size `k`.
- Define a custom `Comparator` for the min-heap. The comparison logic is crucial: 
  - If two words have the same frequency, the one that is lexicographically *larger* is considered "smaller" by the comparator. This ensures it will be at the top of the min-heap and be the first to be removed if a tie occurs.
  - Otherwise, the word with the *lower* frequency is considered "smaller".
- Iterate through the keys (unique words) of the frequency map.
- For each word, `offer` it to the heap. 
- If the heap's size exceeds `k`, `poll` the top element. This removes the element with the lowest frequency (or the lexicographically largest among those with the lowest frequency), maintaining the top `k` candidates in the heap.
- After iterating through all words, the heap contains the `k` most frequent words.
- Since it's a min-heap, the final result needs to be reversed. Dequeue all elements from the heap into a list and then reverse the list.

# Solutions
### Java

```java
public class Top_K_Frequent_Words { public static void main ( String [] args ) { Top_K_Frequent_Words out = new Top_K_Frequent_Words (); Solution s = out . new Solution (); System . out . println ( s . topKFrequent ( new String []{ "the" , "day" , "is" , "sunny" , "the" , "the" , "the" , "sunny" , "is" , "is" }, 4 )); System . out . println ( s . topKFrequent ( new String []{ "i" , "love" , "leetcode" , "i" , "love" , "coding" }, 2 )); } // ref: https://leetcode.com/articles/top-k-frequent-words/ // using a heap (PQ) // Time Complexity: O(Nlogk), where N is the length of words. // We count the frequency of each word in O(N) time, then we add N words to the heap, each in O(logk) time. // Finally, we pop from the heap up to k times. As k≤N, this is O(Nlogk) in total. // Space Complexity: O(N), the space used to store our count. class Solution { public List < String > topKFrequent ( String [] words , int k ) { Map < String , Integer > count = new HashMap <>(); for ( String word: words ) { count . put ( word , count . getOrDefault ( word , 0 ) + 1 ); } PriorityQueue < String > heap = new PriorityQueue < String >( ( w1 , w2 ) -> count . get ( w1 ). equals ( count . get ( w2 )) ? w2 . compareTo ( w1 ) : count . get ( w1 ) - count . get ( w2 ) ); for ( String word: count . keySet ()) { heap . offer ( word ); if ( heap . size () > k ) heap . poll (); } List < String > result = new ArrayList <>(); while (! heap . isEmpty ()) result . add ( heap . poll ()); Collections . reverse ( result ); return result ; // // below also working // List<String> result = new ArrayList<>(); // for (int i = k - 1; i >= 0; i--) { // result.add(0, heap.poll()); // } // // return result; } } } ############ class Solution { public List < String > topKFrequent ( String [] words , int k ) { Map < String , Integer > cnt = new HashMap <>(); for ( String v : words ) { cnt . put ( v , cnt . getOrDefault ( v , 0 ) + 1 ); } PriorityQueue < String > q = new PriorityQueue <>(( a , b ) -> { int d = cnt . get ( a ) - cnt . get ( b ); return d == 0 ? b . compareTo ( a ) : d ; }); for ( String v : cnt . keySet ()) { q . offer ( v ); if ( q . size () > k ) { q . poll (); } } LinkedList < String > ans = new LinkedList <>(); while (! q . isEmpty ()) { ans . addFirst ( q . poll ()); } return ans ; } }
```

### Python

```python
''' >>> sorted(student_objects, key=attrgetter('grade', 'age')) [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)] ref: https://docs.python.org/3/howto/sorting.html#operator-module-functions ''' class Solution : def topKFrequent ( self , words : List [ str ], k : int ) -> List [ str ]: cnt = Counter ( words ) # multiple comparators "lambda x: (-cnt[x], x)" return sorted ( cnt , key = lambda x : ( - cnt [ x ], x ))[: k ] # why the returned sorted() not a tuple (word, count), but only word? # it's the property of Counter() class # so, also pass OJ: return sorted(cnt.keys(), key=lambda x: (-cnt[x], x))[:k] ''' >>> words = ["i","love","leetcode","i","love","coding"] >>> k = 2 >>> cnt = Counter(words) >>> cnt Counter({'i': 2, 'love': 2, 'leetcode': 1, 'coding': 1}) >>> sorted(cnt, key=lambda x: (-cnt[x], x)) ['i', 'love', 'coding', 'leetcode'] # default, only for keys() >>> sorted(cnt) ['coding', 'i', 'leetcode', 'love'] >>> sorted(cnt.keys()) ['coding', 'i', 'leetcode', 'love'] >>> sorted(cnt.values()) [1, 1, 2, 2] >>> sorted(cnt.items()) [('coding', 1), ('i', 2), ('leetcode', 1), ('love', 2)] ''' ############ ''' >>> words = ["the","day","is","sunny","the","the","the","sunny","is","is"] >>> count = collections.Counter(words) >>> count Counter({'the': 4, 'is': 3, 'sunny': 2, 'day': 1}) >>> >>> count.items() dict_items([('the', 4), ('day', 1), ('is', 3), ('sunny', 2)]) >>> ''' ''' cmp doesn't exist in Python 3. If you really want it, you could define it yourself: def cmp(a, b): return (a > b) - (a < b) ''' class Solution ( object ): #python-2 def topKFrequent ( self , words , k ): """ :type words: List[str] :type k: int :rtype: List[str] """ count = collections . Counter ( words ) # https://docs.python.org/3/howto/sorting.html#comparison-functions def compare ( x , y ): if x [ 1 ] == y [ 1 ]: return cmp ( x [ 0 ], y [ 0 ]) else : return - cmp ( x [ 1 ], y [ 1 ]) # -cmp, so reversed order, bigger ones at front return [ x [ 0 ] for x in sorted ( count . items (), cmp = compare )[: k ]]
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/top-k-frequent-words/ // Time: O(NlogK) // Space: O(N) class Solution { public: vector < string > topKFrequent ( vector < string >& A , int k ) { unordered_map < string , int > m ; for ( auto & s : A ) m [ s ] ++ ; auto cmp = [ & ]( auto & a , auto & b ) { return m [ a ] == m [ b ] ? a < b : m [ a ] > m [ b ]; }; priority_queue < string , vector < string > , decltype ( cmp ) > pq ( cmp ); for ( auto & [ s , cnt ] : m ) { pq . push ( s ); if ( pq . size () > k ) { pq . pop (); } } vector < string > ans ; while ( pq . size ()) { ans . push_back ( pq . top ()); pq . pop (); } reverse ( begin ( ans ), end ( ans )); return ans ; } };
```