> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/top-k-elements-heap-bucket-sort/692.-top-k-frequent-words.md).

# 692. Top K Frequent Words

T: O(nlogk)

S: O(n)

````java
```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)

```java
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

 */
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/top-k-elements-heap-bucket-sort/692.-top-k-frequent-words.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.