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

Implementation:

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:

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

PQ offer& poll O(logN)

Space Comp:

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