How do you solve Top K Frequent Words on LeetCode?

Top K Frequent Words (LeetCode #692) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log k) time complexity and O(n) space complexity. Key insight: Using a heap allows us to efficiently manage the top k elements without sorting the entire list.

What are the interview tips for Top K Frequent Words?

Always clarify the problem requirements and constraints before jumping into coding. Discuss your thought process and potential approaches with the interviewer. Consider edge cases, such as when k equals the number of unique words.

What are common mistakes when solving Top K Frequent Words?

Not considering how to handle ties in frequency correctly. Forgetting to reverse the result after extracting from a min-heap.

Top K Frequent Words — LeetCode #692 (Medium)

Tags: Array, Hash Table, String, Trie, Sorting, Heap (Priority Queue), Bucket Sort, Counting

Related patterns: Hash Map, Heap (Priority Queue)

Brute Force approach

Time complexity: O(n²). Space complexity: O(n).

The brute force approach involves counting the frequency of each word and then sorting the entire list of words based on their frequency and lexicographical order. This method is straightforward but inefficient for larger datasets.

The time complexity is O(n²) due to the sorting step, which is inefficient for larger datasets. We count frequencies in O(n) and sort in O(n log n), but in the worst case, sorting could take O(n²) if we use a simple sort algorithm.

Step 1: Count the frequency of each word using a dictionary.
Step 2: Sort the dictionary items first by frequency (in descending order) and then by word (in ascending order).
Step 3: Extract the top k words from the sorted list.

1. Input: words = ["i", "love", "leetcode", "i", "love", "coding"] 2. Count: {"i": 2, "love": 2, "leetcode": 1, "coding": 1} 3. Sorted: [("i", 2), ("love", 2), ("coding", 1), ("leetcode", 1)] 4. Extract top 2: ["i", "love"]

Optimal Solution approach

Time complexity: O(n log k). Space complexity: O(n).

The optimal approach uses a heap (priority queue) to efficiently keep track of the top k frequent words. This reduces the sorting overhead and allows us to maintain only the necessary elements.

The time complexity is O(n log k) because we maintain a min-heap of size k, which allows us to efficiently keep track of the top k elements. Counting frequencies takes O(n), and each insertion into the heap takes O(log k).

Step 1: Count the frequency of each word using a dictionary.
Step 2: Use a min-heap to keep track of the top k elements based on frequency and lexicographical order.
Step 3: Extract the elements from the heap and return them in the required order.

1. Input: words = ["i", "love", "leetcode", "i", "love", "coding"] 2. Count: {"i": 2, "love": 2, "leetcode": 1, "coding": 1} 3. Min-Heap: Add "i" -> ["i"] 4. Min-Heap: Add "love" -> ["i", "love"] 5. Min-Heap: Add "leetcode" -> ["i", "love", "leetcode"] (remove "leetcode") 6. Min-Heap: Add "coding" -> ["i", "love", "coding"] (remove "coding") 7. Result: ["i", "love"]

Key Insights

Using a heap allows us to efficiently manage the top k elements without sorting the entire list.
Sorting by frequency and then lexicographically can be achieved with custom sorting functions.

Common Mistakes

Not considering how to handle ties in frequency correctly.
Forgetting to reverse the result after extracting from a min-heap.

Interview Tips

Always clarify the problem requirements and constraints before jumping into coding.
Discuss your thought process and potential approaches with the interviewer.
Consider edge cases, such as when k equals the number of unique words.

#692

Top K Frequent Words

Medium

Array↗Hash Table↗String↗Trie↗Sorting↗Heap (Priority Queue)↗Bucket Sort↗Counting↗Hash Map↗Heap (Priority Queue)↗

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log k)
Space	O(n)	O(n)

💡

Intuition

Time O(n log k)Space O(n)

The optimal approach uses a heap (priority queue) to efficiently keep track of the top k frequent words. This reduces the sorting overhead and allows us to maintain only the necessary elements.

⚙️

Algorithm

3 steps

1Step 1: Count the frequency of each word using a dictionary.
2Step 2: Use a min-heap to keep track of the top k elements based on frequency and lexicographical order.
3Step 3: Extract the elements from the heap and return them in the required order.

solution.py6 lines

1from collections import Counter
2import heapq
3
4def topKFrequent(words, k):
5    count = Counter(words)
6    return heapq.nsmallest(k, count.keys(), key=lambda x: (-count[x], x))

ℹ

Complexity note: The time complexity is O(n log k) because we maintain a min-heap of size k, which allows us to efficiently keep track of the top k elements. Counting frequencies takes O(n), and each insertion into the heap takes O(log k).

1Using a heap allows us to efficiently manage the top k elements without sorting the entire list.
2Sorting by frequency and then lexicographically can be achieved with custom sorting functions.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.