My simple Java solution using HashMap & PriorityQueue - O(nlogk) time & O(n) space


  • 13
    S

    The idea is to keep a count of each word in a HashMap and then insert in a Priority Queue.
    While inserting in pq, if the count of two words is same then insert based on string compare of the keys.

    class Solution {
        public List<String> topKFrequent(String[] words, int k) {
            
            List<String> result = new LinkedList<>();
            Map<String, Integer> map = new HashMap<>();
            for(int i=0; i<words.length; i++)
            {
                if(map.containsKey(words[i]))
                    map.put(words[i], map.get(words[i])+1);
                else
                    map.put(words[i], 1);
            }
            
            PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
                     (a,b) -> a.getValue()==b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue()-b.getValue()
            );
            
            for(Map.Entry<String, Integer> entry: map.entrySet())
            {
                pq.offer(entry);
                if(pq.size()>k)
                    pq.poll();
            }
    
            while(!pq.isEmpty())
                result.add(0, pq.poll().getKey());
            
            return result;
        }
    }
    

  • 0
    T

    Just wondering how to analyze the complexity of your algorithm? Why it is O(nlogk)?


  • 2
    S

    @tigermlt The size of the priority queue is k. Each insertion takes logk time and we are iterating over n distinct words in the worst case and inserting them into the priority queue which makes the total runtime nlogk.


  • 3
    F
    class Solution {
        public List<String> topKFrequent(String[] words, int k) {
            HashMap<String, Integer> map = new HashMap<>();
            int max = 0;
            for (String w: words) {
                map.put(w, map.getOrDefault(w, 0) + 1);
                max = Math.max(max, map.get(w));
            }
            List<String>[] bucket = new ArrayList[max + 1];
            for (Map.Entry<String, Integer> entry: map.entrySet()) {
                int fre = entry.getValue();
                if (bucket[fre] == null) {
                    bucket[fre] = new ArrayList<>();
                }
                bucket[fre].add(entry.getKey());
            }
            List<String> res = new ArrayList<>();
            for (int i = max; i >= 0 && res.size() < k; i--) {
                if (bucket[i] != null) {
                    Collections.sort(bucket[i]);
                    res.addAll(bucket[i]);
                }
            }
            return res.subList(0, k);
        }
    }
    

  • -1

    I am wondering that you call HashMap + PriorityQueue = O(n) space complexity. Yes, it is O(2n) and we can call it O(n) but...


  • 2
    P

    what does a and b represent in the following line?

    (a,b) -> a.getValue()==b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue()-b.getValue()
    

    is a the minimum value in pq?


  • 1

    I am little confused.
    Why not we choose the solution of O(k * logn) time? As n is bigger than k. It's more efficient, right?

    Just by initialize the queue (O(n)), then pop the first k elements(O(k * logn))?


  • 1
    Q

    @peterysc OP was using the lambda expression which was introduced in Java 8.

    This line sorts the keys alphabetical when they have same frequency (value).

    Here is another example for the lambda expression: https://www.mkyong.com/java8/java-8-lambda-comparator-example/


  • 0
    L

    @peterysc This line is lambda expression, a and b is parameter. It is similar to the following line:

    (Map.Entry<String, Integer> a, Map.Entry<String, Integer> b) -> a.getValue()==b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue()-b.getValue()

    The declaration of type is optional. Also,

    class Cmp implements Comparator<Map.Entry<String, Integer>> {
    @Override
    public int compare(Map.Entry<String, Integer> a, Map.Entry<String, Integer> b) {
    if (a.getValue().equals(b.getValue())) {
    return b.getKey().compareTo(a.getKey());
    }
    return a.getValue() - b.getValue();
    }
    }


Log in to reply
 

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