> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/hashtable/top-k-frequent-words.md).

# Top K frequent words

Given a composition with different kinds of words, return a list of the top K most frequent words in the composition.

**Assumptions**

* the composition is not null and is not guaranteed to be sorted
* K >= 1 and K could be larger than the number of distinct words in the composition, in this case, just return all the distinct words

**Return**

* a list of words ordered from most frequent one to least frequent one (the list could be of size K or smaller than K)

**Examples**

* Composition = \["a", "a", "b", "b", "b", "b", "c", "c", "c", "d"], top 2 frequent words are \[“b”, “c”]
* Composition = \["a", "a", "b", "b", "b", "b", "c", "c", "c", "d"], top 4 frequent words are \[“b”, “c”, "a", "d"]
* Composition = \["a", "a", "b", "b", "b", "b", "c", "c", "c", "d"], top 5 frequent words are \[“b”, “c”, "a", "d"]

**Solution:** HashMap + PQ

I**mplementation:**

```
public class Solution {
  public String[] topKFrequent(String[] combo, int k) {
    if (combo.length == 0) return new String[]{};
    HashMap<String, Integer> count = new HashMap<String, Integer>();

    //all elements into hashMap
    for (String cur: combo){
      count.put(cur, count.getOrDefault(cur, 0) + 1);
    }

    Queue<String> heap = new PriorityQueue<String>(k, new Comparator<String>(){
      @Override
      public int compare(String s1, String s2){
        if (count.get(s1).equals(count.get(s2))) return 0;
        return count.get(s2) - count.get(s1);
      }
    });

    for (String cur: count.keySet()){ //get set of keys in HashMap
      heap.offer(cur);
    }

    if (k > heap.size()) k = heap.size();
    String[] result = new String[k];
    for (int i = 0; i < result.length; i++){
      result[i] = heap.poll();
    }

    return result;
  }

}
```

**Time Comp:**&#x20;

HashMap put & get O(1) most of the time

PQ offer& poll O(logN)

**Space Comp:**

O(PQ + HashMap) = O(K + N)