692. Top K Frequent Words

// LeetCode URL: https://leetcode.com/problems/top-k-frequent-words/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeSet;

/**
 * Find the frequency of each word in words array and use Priority Queue to find
 * top k words.
 *
 * Time Complexity: O(N + N' log K)
 *
 * Space Complexity: O(N' + K). K is always less than or equal to N'. Thus the
 * final space complexity: O(N')
 *
 * N = Length of input array. K = input k. N' = Number of unique words.
 */
class Solution1 {
    public List<String> topKFrequent(String[] words, int k) {
        LinkedList<String> result = new LinkedList<>();
        if (words == null || words.length == 0 || k <= 0) {
            return result;
        }

        HashMap<String, Integer> map = new HashMap<>();
        for (String w : words) {
            map.put(w, map.getOrDefault(w, 0) + 1);
        }

        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>(k + 1,
                (a, b) -> (a.getValue().equals(b.getValue()) ? b.getKey().compareTo(a.getKey())
                        : a.getValue() - b.getValue()));

        for (Map.Entry<String, Integer> e : map.entrySet()) {
            queue.offer(e);
            if (queue.size() > k) {
                queue.poll();
            }
        }

        while (!queue.isEmpty()) {
            result.addFirst(queue.poll().getKey());
        }
        return result;
    }
}

/**
 * Using Bucket Sort
 *
 * Time Complexity: O(N + N' log N')
 *
 * Space Complexity: O(N')
 *
 * N = Length of input array. N' = Number of unique words.
 */
class Solution2 {
    public List<String> topKFrequent(String[] words, int k) {
        ArrayList<String> result = new ArrayList<>();
        if (words == null || words.length == 0 || k <= 0) {
            return result;
        }

        HashMap<String, Integer> map = new HashMap<>();
        for (String w : words) {
            map.put(w, map.getOrDefault(w, 0) + 1);
        }

        HashMap<Integer, TreeSet<String>> buckets = new HashMap<>();

        for (String w : map.keySet()) {
            int freq = map.get(w);
            if (!buckets.containsKey(freq)) {
                buckets.put(freq, new TreeSet<>());
            }
            buckets.get(freq).add(w);
        }

        int cnt = 0;

        for (int i = words.length; i > 0 && cnt < k; i--) {
            if (!buckets.containsKey(i)) {
                continue;
            }
            for (String w : buckets.get(i)) {
                result.add(w);
                cnt++;
                if (cnt == k) {
                    break;
                }
            }
        }

        return result;
    }
}