Efficient PriorityQueue with HashMap, detailed explanation.

  • 0

    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>>() {
    			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()) {
                if (minHeap.size() > k) {
            List<String> ret = new ArrayList<>();
            while (!minHeap.isEmpty()) {
            return ret;

Log in to reply

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