Top K Frequent Words — LeetCode 692 Python Solution
MediumTrieArrayHash TableStringBucket SortCountingSortingHeap (Priority Queue)
- Problem
- #692
- Pattern
- Trie
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest.
Example
- Input
- words = ["i","love","leetcode","i","love","coding"], k = 2
- Output
- ["i","love"]
- Explanation
- "i" and "love" are the two most frequent words.
Python solution
Python
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
cnt = Counter(words)
return sorted(cnt, key=lambda x: (-cnt[x], x))[:k]Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(n) auxiliary |
Pattern: Trie
Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 692. Top K Frequent Words is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.
The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 692. Top K Frequent Words?
- LeetCode 692. Top K Frequent Words is rated Medium on LeetCode.
- What is the time complexity of LeetCode 692. Top K Frequent Words?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 692. Top K Frequent Words?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 692. Top K Frequent Words cover?
- LeetCode 692. Top K Frequent Words is tagged Trie, Array, Hash Table, String, Bucket Sort, Counting, Sorting and Heap (Priority Queue) on LeetCode.