Efficient PriorityQueue with HashMap, detailed explanation.


  • 0
    Y

    The idea itself is straightforward. Since we want to get the top K words, we can simply keep a minimum heap of size K. And this heap should compare the elements in it based on its frequency in words[] first, and if with the same frequency, compare them based on alphabetical order. We could achieve this via a custom Comparator implementation.

    Hence after putting every word in the Heap of size K, whatever left in the heap is the top K word we want.

    In the following implementation I make use of Map.Entry class intensively. Hence keeping the <word, frequency> information together whenever I need them, improved the efficiency of the code.

    Time complexity: O(nlogK) where n is the length of the input words[] array.
    This is due to the Heap is of size K, and we put in/out for a total of n times.

    Space complexity: O(n) because of the map used.

    class Solution {
        public List<String> topKFrequent(String[] words, int k) {
            Map<String, Integer> map = new HashMap<>();
            for (String word : words) {
                if (map.get(word) == null) {
                    map.put(word, 0);
                }
                map.put(word, map.get(word) + 1);
            }
            
            PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>() {
    			@Override
    			public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
    				if (e1.getValue() != e2.getValue()) {
    					return e1.getValue().compareTo(e2.getValue());
    				} else {
    					return e2.getKey().compareTo(e1.getKey());
    				}
    			}
            }); 
            
            for (Map.Entry<String, Integer> entry : map.entrySet()) {
                minHeap.offer(entry);
                if (minHeap.size() > k) {
                    minHeap.poll();
                }
            }
            List<String> ret = new ArrayList<>();
            while (!minHeap.isEmpty()) {
            	ret.add(minHeap.poll().getKey());
            }
            
            Collections.reverse(ret);
            return ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.