692. Top K Frequent Words

T: O(nlogk)

S: O(n)

```java
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        int n = words.length;
        Map<String, Integer> freq = new HashMap<>();
        for (String w : words) {
            freq.put(w, freq.getOrDefault(w, 0)+1);
        }

        // small count pop first, and lexicographical order larger pop first, so that's why b.compareTo(a)
        Queue<String> pq = new PriorityQueue<>((a, b) -> freq.get(a).equals(freq.get(b)) ? b.compareTo(a) : freq.get(a) - freq.get(b));
        for (String key :freq.keySet()) {
            pq.offer(key);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        List<String> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }
        Collections.reverse(result);
        return result;
    }
    
}
/**
bucket + list

seems still nlognc
T: O(n*)

 */
```

Trie + bucket

this question, because it ask, if freq count are the same, return list by lexico order smaller, that's why need Trie

if don't care this, we can only use bucket and list to give ans (like 347 bucket solution)

T: O(n)

S: O(n)

class Solution {
    class TrieNode {
        TrieNode[] children;
        String word;
        TrieNode() {
            children = new TrieNode[26];
        }
    }
    class Trie {
        private TrieNode root = new TrieNode();
        public void buildTrie(String w) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.word = w;
        }
        public void getWords(TrieNode node, List<String> bucketWords) {
            if (node == null) {
                return;
            }
            if (node.word != null) {
                bucketWords.add(node.word);
            }
            for (int i = 0; i < 26; i++) {
                TrieNode child = node.children[i];
                getWords(child, bucketWords);
            }
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        int n = words.length;
        Map<String, Integer> freq = new HashMap<>();
        for (String w : words) {
            freq.put(w, freq.getOrDefault(w, 0)+1);
        }

        Trie[] buckets = new Trie[n+1];
        for (String key : freq.keySet()) {
            int freqCount = freq.get(key);

            if (buckets[freqCount] == null) {
                buckets[freqCount] = new Trie();
            }
            buckets[freqCount].buildTrie(key);
        }

        List<String> result = new ArrayList<>();
        for (int i = buckets.length-1; i >= 0; i--) {
            if (buckets[i] != null) {
                List<String> bucketWords = new ArrayList<>();
                buckets[i].getWords(buckets[i].root, bucketWords);
                int idx = 0;
                while (k > 0 && idx < bucketWords.size()) {
                    result.add(bucketWords.get(idx));
                    k--;
                    idx++;
                }
            }
            if (k == 0) {
                break;
            }
        }
        return result;
    }
    
}
/**
TireNode bucket -> n

 */